Сортировка массивов

Сортировка – это упорядочивание последовательности элементов по заданному признаку. Например, дано множество чисел {5, 2, 4, 3, 1, 0, 6, 7, 9, 8}, т после выполнения сортировки по возрастанию будет получено множество {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

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

1. Сортировка выбором. Дана последовательность чисел a₁,a₂,…,a_n. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый — на место наибольшего. Затем, начиная со второго, эта процедура повторяется. Написать алгоритм сортировки выбором.
2. Сортировка обменами. Дана последовательность чисел a₁,a₂,…,a_n.  Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа а_i и а_i+1 . Если а_i > а_i+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не станут расположены в порядке возрастания. Составить алгоритм сортировки, подсчитывая при этом количество перестановок.
3. Сортировка вставками. Дана последовательность чисел a₁,a₂,…,a_n. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть a₁,a₂,…,a_i упорядоченная последовательность, т.е. а₁ < а₂ < ... < а_i, Берется следующее число а_i+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны.
4. Сортировка Шелла. Дан массив n действительных чисел. Требуется упорядочить его по возрастанию. Делается это следующим образом: сравниваются два соседних элемента а_i и а_i+1. Если а_i < а_i+1, то продвигаются на один элемент вперед. Если а_i > а_i+1, то производится перестановка и сдвигаются на один элемент назад. Составить алгоритм этой сортировки.
5. Алгоритм фон Неймана. Упорядочить массив a₁,a₂,…,a_n по неубыванию с помощью алгоритма сортировки слияниями:

-каждая пара соседних элементов сливается в одну группу из двух элементов (последняя группа может состоять из одного элемента);

-каждая пара соседних двухэлементных групп сливается в одну четырехэлементную группу и т.д.

     При каждом слиянии новая укрупненная группа упорядочивается.

Рассмотрим алгоритм сортировки методом обмена:

Var a: array[1..100] of integer;

I, j, l, n: integer;

Begin

Writeln(‘введите размер массива’);

Readln (n);

For I:=1 to n do read(a[I]);

{проведем сортировку}

repeat

 I:=0;

for j:=1 to n-1 do

if a[j]>a[j+1] then begin l:=a[j]; a[j]:=a[j+1]; a[j+1]:=l;I:=I+1;end;

until I=0;

{выведем полученный массив}

for I:=1 to n do write(a[I],’ ‘,);

end.

 Задача 1. Выполнить сортировку массива по убыванию.

Решение:

repeat

 I:=0;

for j:=1 to n-1 do

if a[j]<a[j+1] then begin l:=a[j]; a[j]:=a[j+1]; a[j+1]:=l;I:=I+1;end;

until I=0;