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

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

2. Меняем местами с первым

3. Этот процесс повторяем с оставшимися n-1 элементами, n-2 и тд элементами до тех пор, пока не останется один самый большой элемент массива.

8 4 9 2 15 1 7

1 4 9 2 15 8 7

1 2 9 4 15 8 7

1 2 4 9 15 8 7

1 2 4 7 15 8 9

1 2 4 7 8 15 9

1 2 4 7 8 9 15

{ai}_N,N

I=0÷(N-1)

Массив отсортирован

Min=ai

k=i

j=i÷N-1

aiak

j>n

Min=>aj

Min=aj

K=j

+

-

Сортировка с помощью прямого обмена

Обмен местами двух элементов. Как и в методе прямого выбора будет повторять проход по массиву справа на лево. Сдвигая каждый раз наименьший элемент к левому концу массива. Метод называется пузырьковой сортировкой. Элемент это выталкиваемый пузырек на уровень соответствующей его весу. Вес соответствует уровню

I=2÷N

Массив

отсортирован

9 2 7 1 5 3 6 b:Boolean;

1 9 2 7 3 5 6

Down to

J=n÷i

1 2 9 3 7 5 6 b=False if not B then break

1 2 3 9 5 7 6

1 2 3 5 9 6 7

aj<aj-1

1 2 3 5 6 9 7

1 2 3 5 6 7 9

ajaj-1

B:=true

Оптимизация алгоритмов пузырьковой сортировки

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

В алгоритме просматривается некоторая асимметрия: один плохо расположенный пузырек на тяжелом конце массива встанет на свое место за один проход. Но если пузырек на легком конце (большой слева) то он подвинется на 2 шаг при каждом проходе. Следовательно, оптимально чередовать направление проходов массива. Получившийся алгоритм называется Шейкерной сортировкой.

L=2; R=N; K=N

Отсортируем массив

J=R÷L

L=k+1

A:array [L..R] of … L 2 3 3 4 4 R 8 8 7 7 6 repeat Направл.

aj<aj-1

ajaj-1;

k=j

j=L÷R

aj<aj-1

ajaj-1;

k=j

R=k-1

L>R

Массив отсортирован

44 06 06 06 06    - 55 44 44 12 12 12 55 12 44 18                  +       -                          42 12 42 18 42 94 42 55 42 44                                                      +                 + 18 94 18 55 55    06 18 67 67 67 67 67 94 94 94

Улучшенный метод сортировки

1. Сортировка шелла – с помощью включений с уменьшающимися расстояниями. Рассмотрим на примере.

44 55 12 42 94 18 06 67

44 18 06 42 94 55 12 67 – четверная сортировка

06 18 12 42 44 55 94 67 – 2-я 06 12 18 42 44 55 67 94 – 1-я

Сначала группируются и сортируются элементы, стоящие друг от друга.

Либо сортируются относительные элементы, либо элементы уже довольно хорошо упорядоченные. Следовательно, понадобится мало перестановок. Каждая I ая перестановка объединяет две группы уже отсортированы. Расстояние в группах можно уменьшать по-разному (последнее расстояние должно быть единичным).

h₁,h₂,..,ht; ht=1 hi+1<hi

Неизвестно какие расстояния дают наилучший результат. Они не должны быть множителями одного другого.

h_k-1=2*hk-1

Каждая h-я сортировка программируется как сортировка с помощью прямого включения причем условие окончания поиска места включения обеспечивается методом барьера. Расширяем массив на h1 элементов

A:array[-h1..n] of integer;

m=1÷t

s=0

h₁=9; h₂=5; h₃=3; h₄=1

s=-k

Массив отсорт.

- +

s=s+1

a_s=x

А

k=h_m; s=-k

x<aj

j=k+1÷N

aj+k=x

А -

x=a_i

j=i-k

aj+1=aj

j=j-1

+