Сортировка бинарными включениями

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

Суть метода заключается в следующем:

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

Текстовый алгоритм:

1. Начало.

2. Выполнить цикл, пока I имеет значение от 2 до N с шагом = 1

а) X = A(i), l = 1, r = i-1

б) Если l > r, то:

1) выполнить цикл, пока j имеет значение от (i-1) до l с шагом = -1

тело цикла: A(j + 1) = A(j)

2) присвоить A(l) = X

иначе:

1) присвоить m = (l + r) \ 2

2) если X < A(m), то r = m – 1 иначе l = m + 1

3) перейти к пункту б).

3. Конец.

На рисунке 7 приведен пример выполнения сортировки бинарными включениями.

Исходная последовательность	44	55	12	42	94	18	06	67
I = 2	4 4	55	12	42	94	18	06	67
I = 3	12	4 4	55	42	94	18	06	67
I = 4	12	42	44	55	9 4	18	06	67
I = 5	12	4 2	44	55	94	18	06	67
I = 6	1 2	18	42	44	55	94	06	67
I = 7	06	12	18	42	44	55	9 4	67
I = 8	06	12	18	42	44	55	67	94
Результат	06	12	18	42	44	55	67	94

Рис. 7. Пример выполнения сортировки бинарными включениями

На рисунке 8 представлена блок-схема сортировки бинарными включениями.

Рис. 8. Блок-схема сортировки бинарными включениями

Шейкер – сортировка

Как и алгоритм сортировки прямого обмена, алгоритм шейкер – сортировки основан на сравнении и смене мест пары соседних элементов. Однако в рассматриваемом методе каждый шаг состоит из двух этапов.

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

Текстовый алгоритм:

1. Начало.

2. Присвоить переменной t (слева массива) значение 2, переменной r (справа массива) и переменной k – значение количества элементов массива.

3. Выполнить цикл, пока i имеет значение от r до t с шагом = -1:

а) если A(i-1) > A(i), то меняем местами эти два элемента и переменной k присваиваем значение = i.

4. Присвоить переменной t значение = k + 1.

5. Выполнить цикл, пока i имеет значение от t до r с шагом = 1:

а) если A(i-1) > A(i), то меняем местами эти два элемента и переменной k присваиваем значение = i.

6. Присвоить переменной r значение = k – 1.

7. Если t > r, то идти к пункту 8, иначе идти к пункту 3.

8. Конец.

На рисунке 9 представлен пример выполнения шейкер – сортировки по шагам.

Исходная последовательность		4 4	55	12	42	94	18	06	67
1-й шаг	1-й этап	06	44	55	1 2	42	9 4	18	67
	2-й этап	06	44	12	42	55	18	67	94
2-й шаг	1-й этап	06	12	44	18	42	55	67	94
	2-й этап	06	12	18	42	44	55	67	94
3-й шаг	1-й этап	06	12	18	42	44	55	67	94
Результат		06	12	18	42	44	55	67	94

Рис. 9. Пример выполнения шейкер – сортировки

На рис. 10 приведена блок-схема шейкер – сортировки.

Рис. 10. Блок-схема шейкер – сортировки

Из примера, приведенного на рисунке 9 видно, что после первого шага длина неотсортированной части уменьшилась на два элемента, а после второго шага длина неотсортированной части вместо двух уменьшилась сразу на 4 элемента. Это дополнительное уменьшение обеспечивает переменная k, показывающая при каком значении i был совершен последний обмен местами двух элементов. Благодаря переменной k быстрее увеличивается и быстрее уменьшается левая (t = k + 1) и правая (r = k – 1) границы неотсортированной части.