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

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

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

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

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

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

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

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

Таким образом, на 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 сравнений

и снова две операции перемен элементов местами. Значит, всего (в худшем случае)выполняется(n 2+ 3 n)/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

Дата добавления: 2015-11-16