4.3. Сортировка выбором

Метод сортировки с выбором напоминает сортировку пузырьковым

методом. Вначале неотсортированным полагают весь исходный массив. В

процессе сортировки находится наименьший элемент, содержащийся в

рассматриваемой (неотсортированной) части массива, который помещается

взамен его первого элемента. Затем процедура повторяется — рассматривается

неотсортированная часть массива, которая уменьшена по сравнению с пре-

дыдущей итерацией на одинэлемент.

Таким образом, на k -й итерации, как и в пузырьковой сортировке, рассматривают массив а_k_, ..., а_п_и, найдя в нем наименьший элемент,

меняют его местами с элементом а[к]. Следовательно, сортировка заканчивается после выполнения n 1-й итерации.

Пример 4.3.1. Сортировкой выбором упорядочитьмассив

А = {8, 4, 6, 3, 7, 2, 1, 5}.

Изменения исходного массива в процессе сортировки представлены в виде

последовательности массивов, каждый из которых есть результат

соответствующей итерации

{8, 4, 6, 3, 7, 2, 1, 5}

{1, 4, 6, 3, 7, 2, 8, 5}

{1, 2, 6, 3, 7, 4, 8, 5}

{1, 2, 3, 6, 7, 4, 8, 5}

исходный массив;

1-я итерация;

2-я итерация;

3-я итерация;

{1, 2, 3, 4,

{1, 2, 3, 4,

{1, 2, 3, 4,

{1, 2, 3, 4,

7, 6, 8, 5}

5, 6, 8, 7}

5, 6, 8, 7}

5, 6, 7, 8}

4-я итерация;

5 -я итерация;

6 -я итерация;

7 -я итерация;

Определим числоопераций, необходимыхдля сортировки.

На первой итерации требуется, очевидно, выполнить п -1 сравнений и

две операции перемен двух элементов местами. На второй итерации уже

требуется выполнить п-2 сравнений и две операции перемещений элементов. Легко заметить, что на k -й итерации необходимо выполнить n k сравнений

и снова две операции перемен элементов местами. Значит, всего (в худшем ^{случае) выполняется} ^{n2 3n}^{/2 2операций.}

Программа сортировки выбором на Паскале может иметь следующий вид:

program Select;

(* сортировка выбором *) Uses CRT;

Const n=8;

Var

I,j,k,t :integer; flag :boolean;

A :array[l..n] of integer;

begin clrscr;

for i:=l to n do A[i]:=0;

writeln ('Введите элементы массива'); for i:=l to n do

read(A[i]) Writeln;

k:=l; (* номер итерации *) j:=l;

repeat flag:=false;

Writeln (k,’-тая итерация’); t:=A[k];

for i:=k to n do if A[i]<t then begin flag:=true; t:=A[i]

j:=i; end;

if flag then begin A[j]:=A[k]; A[k]:=t; end;

for i:=l to n do Write(A[i],' '); Writeln;

k:=k+l; until(k=n);

;

;

end.

Лекция 5