Словесное описание алгоритма.

0. В готовую подпоследовательность записывается а₁, во входную – а₂,....а_n.

1. i = 2.

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

а) расширяем готовую подпоследовательность слева: а₀ = х - барьер;

 

б) просматривая элементы готовой подпоследоватепьности слева направо,
находим такой номер j что и a_i <= x < a_{i +1};

в) если j = j - 1, то переходим к пункту г), иначе расширяем готовую
подпоследовательность справа, сдвигая ее элементы, начиная с a_i вправо;

г) a_i+1 = x

д) i = i + 1. Если i <=n, то переходим к п.2, иначе сортировка заканчивается..

Таблица 4.1

Начальные ключи	44	55	12	42	94	18	06	67
i = 2	44	55	12	42	94	18	06	67
i = 3	12	44	55	42	94	18	06	67
i = 4	12	42	44	55	94	18	06	67
i = 5	12	42	44	55	94	18	06	67
i = 6	12	18	42	44	55	94	06	67
i = 7	06	12	18	42	44	94	94	67
i = 8	06	12	18	42	44	55	67	94

 

Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность а₂,....а_n, в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарной поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Словесное описание алгоритма

0. В готовую подпоследовательность записывается а₁, во входную а₂,....а_n.

1. i = 2

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

а) организуем бинарный поиск места включения х в готовую подпоследовательность: находим срединный элемент готовой подпоследовательности – a_m, где m =] i/2[, и сравниваем его с х. Если a_m > х то ведем далее поиск в левой половине готовой подпоследовательности, т. е. опять находим срединный элемент и сравниваем его с х и т. д., пока не найдем номер j такой, что a_i <= x < a_i+1, иначе аналогично ведем поиск в правой половине готовой подпоследовательности;

б) если j = j – 1, то переходим к пункту в), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы, начиная с a_i вправо;

в) a_{i +1} = х

3. i=i+1. Если i <= n, то переходим к п.2, иначе сортировка заканчивается.

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

Этот метод основан на следующем правиле:

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

2. Он меняется местами с первым элементом а_i.

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

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

 

Таблица 4.2

Начальные ключи 44 55 12 42 94 18 06 67

                             06    55 12 42 94 18 44 67

                             06 12   55 42 94 18 44 67

                             06 12 18 42 94 55 44 67

.                            06 12 18 42 94 55 44 67

                             06 12 18 42 44 55 94 67

                             06 12 18 42 44 55 94 67

                             06 12 18 42 44 55 67 94