Сортировка выбором
При сортировке выбором выбирается элемент с наименьшим зна- чением и делается его обмен с первым элементом массива. Затем на- ходится элемент с наименьшим значением из оставшихся 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]
k := j;
x := item[j];
end;
item[k] := item[i]; { обмен }
item[i] := x;
end;
end; { конец сортировки выбором }
Вывод числа операций обмена для среднего случая выходит за рамки этой книги. Это число равно n(ln+y), где "y" является конс- тантой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки вы- бором.
