Сортировка включениями

End;

End;

End;

Begin

Var

End;

End;

End;

Begin

End;

Begin

Begin

Var

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

Это простой и наиболее очевидный способ сортировки. Его алгоритм состоит их двух шагов:

q Выбирается элемент с наименьшим ключом

q Меняется местами с первым элементом массива

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

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

Сортировка простым выбором показана в листинге 7.1. Процедура имеет только один параметр – сортируемый массив.

Листинг 7.1. Сортировка простым выбором. Вариант 1

procedure SortSelection(var a: TData);

i,j,imin : integer;

min :integer;

for I:=1 to N – 1 do begin

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

for j:=i+1 to N do // в этом цикле ищем минимальный элемент

if a[j]<min then

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

if i<>imin then

a[imin]:=a[i]; // обмен местами мин. элемента с первым

a[i]:=min // из оставшейся – не отсортированной –

// части массива

Обмен местами двух элементов стандартно выполняется в три действия с использованием третьего – вспомогательного – элемента. Однако в этом примере роль вспомогательного элемента играет переменная min. Эта же переменная, участвуя в сравнении элементов, неявно уменьшает время работы программы, так как доступ к простой переменной осуществляется быстрее, чем к элементу массива.

Для сравнения приводится этот же алгоритм, реализующий вышеприведенные отличия:

Листинг 7.2. Сортировка простым выбором. Вариант 2

procedure SortSelection1(var a: TData);

i,j,imin : integer;

tmp : integer;

for i:=1 to N - 1 do begin

imin:=i;

for j:=i + 1 to N do // в этом цикле ищем минимальный элемент

if a[j]<a[imin] then imin:=j;

if i<>imin then begin

tmp:=a[imin]; // обмен местами мин. элемента с первым

a[imin]:=a[i]; // из оставшейся – не отсортированной

a[i]:=tmp //– части массива

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

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

Число C сравнений ключей не зависит от исходной упорядоченности. C=1/2(N²-N). Число M перестановок минимально в случае изначальной упорядоченности: M~N и принимает наибольшее значение, если ключи изначально расположены в обратном порядке: M~trunc(N²/4)+3(N-1).