Энциклопедия 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.  Это значит,  что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором,  число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.