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

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

Обменная сортировка простой выборкой показана в программном примере 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
1	_11:447 286 708_ 24 242 192 860 937 561
2	_11_24:286 708 447 242 192 860 937 561
3	_11_24 192:708 447 242 286 860 937 561
4	_11_24 192 242:447 708 286 860 937 561
5	_11_24 192 242 286:708 447 860 937 561
6	_11_24 192 242 286 447:708 860 937 561
7	_11_24 192 242 286 447 561:860 937 708
8	_11_24 192 242 286 447 561 708:937 860
9	_11_24 192 242 286 447 561 708 860:937
Результат	_11_24 192 242 286 447 561 708 860 937: