Сортировка посредством выбора
Идея сортировки посредством выбора также проста. На 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-й проход |
1980 | ||||||
1902 | 1963 | |||||
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.
Быстрая сортировка
Данный алгоритм является самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка".[*] В этом алгоритме для сортировки элементов массива А[1], ..., А[n] из этих элементов выбирается некоторое значение ключа v в качестве опорного элемента, относительно которого переупорядочиваются элементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса j все переставленные элементы А[1], ..., A[j] имели значения ключей, меньшие, чем v, а все элементы A[j + 1], ..., А[n] — значения ключей, большие или равные v. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов А[1], ..., A[j] и A[j + 1], ..., А[n] для упорядочивания этих множеств по отдельности. Поскольку все значения ключей в первом множестве меньше, чем значения ключей во втором множестве, то исходный массив будет отсортирован правильно.
Задача 7.13. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством быстрой сортировки.
Листинг программы
program task4;
uses crt;
const n = 10;
type vector = array [ 1..n] of integer;
var a : Vector;
i, j : integer;
temp : integer;
procedure QuickSort;
procedure sort (l, r : integer);
var i, j, w, x : integer;
begin
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while a[i] < x do
i :=i+1;
while a[j] > x do
j := j-1;
if i <= j then
begin
w := a[i];
a[i]:=a[j];
a[j]:=w;
i := i+1;
j := j-1;
end;
until i > j;
if l < j then sort(l,j);
if i < r then sort(i,r);
end;
begin
sort (1,n);
end;
begin
clrscr;
randomize;
for i :=1 to n do
begin
a[i] := random(11)-5;
writeln ('a[', i, ']=', a[i]:3);
end;
quicksort;
writeln ('Отсортированный массив по возрастанию');
for i := 1 to n do
writeln ('a[', i, ']=', a[i]:3);
readln;
end.