Простые методы сортировки массивов: перестановкой, обменом, вставками

Сортировка - это процесс упорядочивания информации по определенному признаку. Цель сортировки - облегчение последующего поиска элементов. Это почти универсальный вид обработки информации, с которым мы встречаемся в жизни повсеместно.

Пример. Разработать программу сортировки элементов массива А(n), где n < 20, используя метод выбора, метод вставки и метод обменов.

Метод выбора. Сортировка посредством выбора представляет собой один из самых простых методов сортировки. Он предполагает такую последовательность действий. Сначала находим минимальный элемент массива. Найденный элемент меняем местами с первым элементом. Затем повторяем процесс с п-1 элементами, начиная со второго, потом с п-2 элементами, начиная с третьего и т.д. до тех пор, пока не останется один, самый большой элемент массива.

Приведем текст программы, реализующий данный алгоритм.

Program sortl;

Var a: array [1..20] of real;

j, i, n, imin: integer;

min:real;

Begin

WritelnCВведите количество чисел п<=20:');

Readln(n);

Writeln('Введите массив:');

for i:=l to n do Read(a[i]);

Readln;

for j:=l to n-1 do {цикл поиска минимальных элементов массива}

begin

min:=a[j]; {начальное значение для поиска минимума}

imin:=j; {начальное значение индекса минимального элемента}

for i:=j+l to n do {цикл поиска минимума и его индекса}

if a[i]<min then {если элемент меньше уже найденного минимального}

begin min:=a[i]; {запоминаем

элемент}

imin:=i {запоминаем его индекс}

end;

{меняем местами найденный минимум и первый элемент текущего массива}

a[imm]:=a[j];

a[j]:=min;

end;

for i:=l to n do Write(a[i]:6:2);

Writeln;

End.

Метод вставки. Сортировку вставками можно описать следующим образом. В исходном состоянии считают, что сортируемая последовательность состоит из двух последовательностей: уже сортированной (она на первом шаге состоит из единственного - первого элемента) и последовательности элементов, которые еще необходимо сортировать. На каждом шаге из сортируемой последовательности извлекается элемент и вставляется в первую последовательность так, чтобы она оставалась сортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемый элемент ai с очередным элементом сортированной последовательности аj. Если элемент ai больше аj, его вставляют вместо aj+1, иначе сдвигают аj вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент ai вставляют на первое место.

Разрабатывая алгоритм, избавимся от проверки достижения начала массива. Прием, позволяющий отменить эту проверку, называется «проверка с барьером». С использованием этого приема проверка организуется так, чтобы из цикла поиска места вставки в любом случае происходил выход по первому условию. Для этого достаточно поместить вставляемый элемент перед первым элементом массива, как элемент с индексом 0. Этот элемент и станет естественным барьером для ограничения выхода за левую границу массива. Приведем текст программы, реализующей данный алгоритм.

Program sort2;

Vara:array[0..20] of real;

B:real;

i,j,n: integer;

Begin

WriteLn('Введите количество чисел п<=20.');

ReadLn(n);

WriteLn('Введите массив.');

for i:=l to n do Read(a[i]);

ReadLn;

for i:-2 to n do {начиная со второго элемента до конца массива}

begin

B:=a[i]; {запоминаем i-й элемент}

а[0]:=В; {этот же элемент записываем в а[0] - это барьер}

j:=i-l; {индекс i запоминаем в j}

while B<a[j] do {пока очередной рассматриваемый элемент больше 1-го элемента} begin

a[j+1]:=a[j]; {сдвигаем элемент}

j:=j-l; {уменьшаем j на 1}

end;

a[j+1]:=B; {как только найдено место, туда записывается В}

end;

WriteLh('Отсортированный массив:');

for i:=l to n do Write(a[i]:6:2);

WriteLn;

End.

Метод обменов. Алгоритм прямого обмена основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнения и перестановки продолжают до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены, можно, считая количество выполненных перестановок: если количество перестановок равно нулю, то массив отсортирован.

Приведем программу, реализующая данный алгоритм.

Program ex;

Var a: array [1..20] of Real;

i,j,n,l,k: integer;

b:real;

Begin

WriteLn( "Введите размер массива N< =20 ');

ReadLn(n);

for i := 1 ton do Read(a[i]);

ReadLn;

WriteLn( 'Исходный массив: ');

for i := 1 to n do Write(a[i]:7:2);

WriteLn;

k:=l; {количество перестановок, начальное значение не равно 0 }

i:=l; {номер очередного просмотра, в начале равен 1 }

while k<>0 do {пока есть перестановки}

begin

k:=0; {обнуляем количество перестановок}

for j:=l to n-l do {цикл сравнения соседних элементов}

if a[j]>a[j+l] then {если предыдущий элемент больше последующего, то}

begin {осуществляем перестановку}

b:=a[j];

a[j]:=a[j+1];

a[j+1]:=b;

k:=k+l; {счетчик перестановок увеличиваем на 1}

end;

i:=i+l; {увеличиваем номер просмотра на 1 }

end;

WriteLn(' Отсортированный массив ');

for i := 1 to n do Write (a[ij:7:2);

WriteLn;

WriteLn(' Количество проходов ', i:3);

End