Алгоритм сортировки выбором и оценка его эффективности

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений.

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка файлов.

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

Удобной мерой эффективности является подсчет числа С — сравнений элементов и М — присваиваний элементов. Достаточно хороший алгоритм затрачивает на сортировку N элементов время порядка N×log₂(N). Простейшие алгоритмы сортировки обладают характеристикой порядка N². Если N достаточно мало, то простые алгоритмы выгодно использовать в силу простоты их реализации.

Имеется три способа сортировки массивов:

• 
  сортировка выбором;
  
• 
  сортировка обменом;
  
• 
  сортировка вставкой.
  

При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:

исходное положение: b d a c;

первый проход: a d b c;

второй проход: a b b c;

третий проход: a b c d.

Процедура, реализующая алгоритм сортировки выбором:

procedure sort(var a : mas; n : byte);

var i, j, min: byte; vsp : integer;

begin

begin

for j := i+1 to n do{найти элемент с наименьшим значением}

if a[j]