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

         -----------------------------------------------------------------

              При сортировке выбором выбирается элемент с наименьшим  зна-

         чением и делается его обмен с первым элементом массива. Затем на-

         ходится элемент с наименьшим значением из оставшихся n-1  элемен-

         тов  и  делается  его обмен со вторым элементом и т.д.  до обмена

         двух последних элементов.  Например, если сортировку выбором при-

         менить для массива "bdac", то будут получены следующие проходы:

         Энциклопедия по Турбо-Паскалю   ч.1                        = 14 =

              - исходное состояние: 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.  Это значит,  что

         несмотря на одинаковое число операций  сравнений  для  сортировок

         пузырьковым  методом и сортировок выбором,  число операций обмена

         для среднего случая будет значительно меньшим для сортировки  вы-

         бором.