7.3.3. Сортировка посредством выбора

Идея сортировки посредством выбора также проста. На i-м этапе сортировки выбирается запись с наименьшим ключом среди записей A[i], ..., А[n] и меняется местами с записью A[i]. В результате после i-гo этапа все записи А[1], ..., A[i] будут упорядочены. Сортировку посредством выбора можно описать следующим образом:

for i: = 1 to n - 1 do

выбрать среди A[i], ..., А[n] элемент с наименьшим ключом и

поменять его местами с A[i];

Более полный код, реализующий этот метод сортировки, приведен в листинге 4.

Листинг 3. Сортировка посредством выбора

var

lowkey: keytype; { текущий наименьший ключ, найденный

при проходе по элементам A[i], ..., А[n] }

lowindex: integer; { позиция элемента с ключом lowkey }

temp : recordtype;

begin

for i:= 1 to n - 1 do begin

lowindex:= i;

lowkey:= A[i].key;

for j:= i + 1 to n do begin

{ сравнение ключей с текущим ключом lowkey}

if A[j].key < lowkey then begin

lowkey:= A[j].key;

lowindex: = j

end;

temp := A[i];

A[i] := A[lowindex];

A[lowindex] := temp;

End; End; End;

Пример 7.3. В табл. 7 показаны этапы сортировки посредством выбора для списка из табл. 5. Например, на 1-м этапе значение lowindex равно 6, т.е. позиции значения 79, которое меняется со значением 1902 , элементом А[1].

Линии в табл. 3 показывают, что элементы, расположенные выше ее, имеют наименьшие значения ключей и уже упорядочены. После (n - 1)-го этапа элемент А[n] также стоит на "правильном" месте, так как выше его все записи имеют меньшие значения ключей.

Таблица 7. Сортировка посредством выбора

i	начальное положение	1-й проход	2-й проход	3-й проход	4-й проход	5-й проход
1	1902	79	79	79	79	79
2	1669	1669	1669	1669	1669	1669
3	1883	1883	1883	1883	1883	1883
4	1963	1963	1963	1963	1902	1902
5	1980	1980	1980	1980	1980	1963
6	79	1902	1902	1902	1963	1980
i		i = 1 low = 6	i = 2 low = 2	i = 3 low = 3	i = 4 low = 6	i = 5 low = 6

Задача 7.12. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством выбора.

Листинг программы

program task3;

uses crt;

const n = 10;

type vector = array [1..n] of integer;

var

a : Vector;

i, j : integer;

temp : integer;

begin

clrscr;

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

for i := 1 to n-1 do

begin

for j := i+1 to n do

begin

if a[j] < a[i] then

begin

temp := a[j];

a[j] := a[i];

a[i] := temp;

end;

end;

end;

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.