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

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

Пример. Разработать программу сортировки элементов массива А(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