Обменная сортировка простой выборкой.

Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется его, так называемый, обменный вариант. При обменной сортировке выборкой входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.

Обменная сортировка простой выборкой показана в программном примере 3.8. Процедура имеет только один параметр - сортируемый массив.

{===== Программный пример 3.8 =====}

Procedure Sort(var a : SEQ);

Var x, i, j, m : integer;

begin

for i:=1 to N-1 do { перебор элементов выходного множества}

{ входное множество - [i:N]; выходное - [1:i-1] }

begin m:=i;

for j:=i+1 to N do { поиск минимума во входном множестве }

if (a[j] < a[m]) then m:=j;

{ обмен 1-го элемента вх. множества с минимальным }

if i<>m then begin

x:=a[i]; a[i]:=a[m]; a[m]:=x;

end;end; end;

Результаты трассировки программного примера 3.8 представлены в таблице 3.5. Двоеточием показана граница между входным и выходным множествами.

Шаг	Содержимое массива а
Исходный	:242 447 286 708_24_11 192 860 937 561
	_11:447 286 708_ 24 242 192 860 937 561
	_11_24:286 708 447 242 192 860 937 561
	_11_24 192:708 447 242 286 860 937 561
	_11_24 192 242:447 708 286 860 937 561
	_11_24 192 242 286:708 447 860 937 561
	_11_24 192 242 286 447:708 860 937 561
	_11_24 192 242 286 447 561:860 937 708
	_11_24 192 242 286 447 561 708:937 860
	_11_24 192 242 286 447 561 708 860:937
Результат	_11_24 192 242 286 447 561 708 860 937: