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

Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - 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;