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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Алгоритм сортировки выбором

Шаги алгоритма:

находим минимальное  значение в текущем списке

производим обмен  этого значения со значением на первой неотсортированной позиции

теперь сортируем  хвост списка, исключив из рассмотрения уже отсортированные элементы

Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.

Существует также  двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются  на свои места и минимальное, и  максимальное значения. 

     Идея  метода состоит в том, чтобы создавать  отсортированную последовательность путем присоединения к ней  одного элемента за другим в правильном порядке.

     Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

     На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

     

     Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким  образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте  по праву: все меньшие элементы уже  ушли влево. 

     Для нахождения наименьшего элемента из n+1 рассматримаемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

     n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2).

     Таким образом, так как число обменов  всегда будет меньше числа сравнений, время сортировки растет квадратично  относительно количества элементов.

     Алгоритм  не использует дополнительной памяти: все операции происходят "на месте".

     Устойчив  ли этот метод ? Прежде, чем читать далее, попробуйте получить ответ самостоятельно.

     Рассмотрим  последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них.

     Результат ее сортировки можно увидеть уже  после шага 0, так как больше обменов  не будет. Порядок ключей 2a, 2b был  изменен на 2b, 2a, так что метод  неустойчив.

     Если  входная последовательность почти  упорядочена, то сравнений будет  столько же, значит алгоритм ведет  себя неестественно. 
 
 
 

     Блок  схема 

       
 
 
 
 

     Код программы

                   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;