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

В массиве a[1..n] находим элемент с минимальным значением и меняем его местами с первым. Во втором проходе находим элемент с минимальным значением в оставшейся части массива, т.е. на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. Продолжая далее этот процесс для всех элементов до (n-1)-го. Такой алгоритм часто называют линейным. Его также можно организовать, используя два вложенных цикла: внешний – для проходов, внутренний – для линейного поиска минимального элемента в соответствующей части массива.

procеdure LineSort_01(var a:vector; n:size);

var i,j,min,imin:size;

begin

for i:=1 to n-1 do begin

{ поиск минимального элемента min }

{ и его индекса в оставшейся части массива }

min:=a[i]; imin:=i;

for j:=i+1 to n do

if min >a [j]

then begin min:=a[j]; imin:=j end;

a[imin]:=a[i]; a[i]:=min

end

end;

Общая сложность алгоритма может быть оценена как .

Необходимо выполнить отладку программы и провести упорядочение массива по возрастанию. Вычислить количество сравнений, которые осуществляются при сортировке массивов большой размерности (n>1000), а также при его переупорядочении.

Составим внутреннюю процедуру поиска минимальных элементов и запишем процедуру сортировки выбором так

procеdure LineSort_02(var a:vector; n:size);

function Min(k:size);

var j,m:size;

begin m:=k;

for j:=k+1 to n do

if a[m] >a [j]

then m:=j;

Min:=m

end;

var i:size;

begin