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

В литературе описано несколько различных модификаций сортировки выбором, но суть их всех заключается в том, что на очередном шаге выбирается необходимый элемент, и он помещается на заданное место в сортируемой последовательности. Рассмотрим одну их модификаций сортировки выбором.

Пусть дан одномерный неупорядоченный массив, содержащий целые числа М={m_i}, i=1,n; n - число элементов. Необходимо упорядочить элементы этого массива по возрастанию их значений.

На первом шаге из элементов массива выбирается минимальный, и он меняется местами с элементом, стоящем на первом месте. На втором шаге из оставшихся неупорядоченных элементов, начиная со второго, выбирается следующий минимальный элемент, и он меняется местами с элементом, стоящем на втором месте. Процесс повторяется до тех пор, пока не будут переставлены все элементы. Последний элемент можно не проверять, так как к этому времени все элементы уже будут стоять на своих местах.

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

Рассмотрим работу алгоритма по схеме.

Схема алгоритма сортировки выбором

нет

да

Min - минимальный элемент

i_min - адрес минимального элемента

Текст программы сортировки выбором

Uses crt;

Var

M:array[1..1000] of integer;

n, i, j, Min, i_min:integer;

Begin

Clrscr;

Write(' Введите длину массива n = ');

Readln(n);

{ Вместо ввода с клавиатуры заполним массив случайными числами из диапазона от 0 до 500}

For i:=1 to n do M[i]:=Random(500);

For i:=1 to n-1 do

Begin

{принимаем за минимум i-й элемент}

Min:=M[i]; i_min:=i;

For j:=i+1 to n do

If M[j]<Min then

Begin

{найдено меньшее число - запоминаем его и его адрес}

Min:=M[j]; i_min:=j;

End;

{Обмен}

M[i_min]:=M[i];

M[i]:=Min;

End;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' ');

readkey;

End.