Энциклопедия Turbo Pascal. Главы 1-4 - Сортировка выбором
ОГЛАВЛЕНИЕ
Сортировка выбором
При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:
- исходное состояние: b d a c;
- первый проход: a d b c;
- второй проход: a b b c;
- третий проход: a b c d.
Ниже приводится простой алгоритм сортировки выбором /см. следующую страницу/.
К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
Это значит, что число сравнений для сортировки выбором равно 1/2
(n** 2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3 (n-1), а в худшем случае равно n**2/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1элементов,а каждая операция обмена требует три операции пересылки.
{ сортировка выбором }
procedure Selekt(var item: DataArray; count:integer);
var
i, j, k: integer;
x: DataItem;
begin
for i := i to count-1 do
begin
k := i;
x := item[i];
for j := i+1 to count do { найти элемент с наименьшим
значением }
if item[j]<x then
begin
k := j;
x := item[j];
end;
item[k] := item[i]; { обмен }
item[i] := x;
end;
end; { конец сортировки выбором }
Вывод числа операций обмена для среднего случая выходит за рамки этой книги. Это число равно n(ln+y), где "y" является константой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.