Сортировка простой выборкой

Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N^2). Количество пересылок - N.

Алгоритм сортировки простой выборкой иллюстрируется программным примером 3.7.

В программной реализации алгоритма возникает проблема значения ключа "пусто". Довольно часто программисты используют в качестве такового некоторое заведомо отсутствующее во входной последовательности значение ключа, например, максимальное из теоретически возможных значений. Другой, более строгий подход - создание отдельного вектора, каждый элемент которого имеет логический тип и отражает состояние соответствующего элемента входного множества ("истина" - "непусто", "ложь" - "пусто"). Именно такой подход реализован в нашем программном примере. Роль входной последовательности здесь выполняет параметр a, роль выходной - параметр b, роль вектора состояний - массив c. Алгоритм несколько усложняется за счет того, что для установки начального значения при поиске минимума приходится отбрасывать уже "пустые" элементы.

{===== Программный пример 3.7 =====}

Procedure Sort(a: SEQ; var b: SEQ);

Var i, j, m: integer;

c: array[1..N] of boolean; {состояние эл-тов вх.множества}

begin

for i:=1 to N do c[i]:=true; { сброс отметок}

for i:=1 to N do {поиск 1-го невыбранного эл. во вх.множестве}

begin j:=1;

while not c[j] do j:=j+1;

m:=j; { поиск минимального элемент а}

for j:=2 to N do

if c[j] and (a[j] < a[m]) then m:=j;

b[i]:=a[m]; { запись в выходное множество}

c[m]:=false; { во входное множество - "пусто" }

end; end;