Энциклопедия Turbo Pascal. Главы 1-4
Страница 6. Сортировка выбором

Сортировка выбором

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