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

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

Обменная сортировка простой выборкой показана в программном примере 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:

Таблица 3.5

Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но порядок алгоритма остается степенным - O(n^2). Количество перестановок N-1, но перестановка, по-видимому, вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.

Довольно простая модификация обменной сортировки выборкой предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума и обмен их с первым и с последним элементами множества соответственно. Хотя итоговое количество сравнений и пересылок в этой модификации не уменьшается, достигается экономия на количестве итераций внешнего цикла.

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