6

4. Сортировка

Цель практического занятия по данной теме - ознакомиться с простейшими методами сортировки и приобрести навыки их использования и оценивания их сложности.

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве.

4.1. Сортировка простыми включениями

Этот метод обычно заключается в следующем. Элементы условно разделяются на готовую последовательность а_i, …а_i-1, и входную последовательность а₁, …а_n. На каждом шаге, начиная с i = 2 и увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" сравнивая его с очередным элементом а и либо вставляя х, либо пересылая а_i направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях:

1. Найден элемент а_i с ключом, меньшим, чем ключ х.

2. Достигнут левый конец готовой последовательности.

Этот типичный пример цикла с двумя условиями окончания дает возможность рассмотреть хорошо известный прием фиктивного элемента ("барьера"). Его можно легко применить в этом случае, обновив барьер а₀ = х. (Заметим, что для этого нужно расширить диапазон индексов в описании а до 0,...,n.)

Процесс сортировки простыми включениями показан в табл. 4.1 на примере восьми случайно взятых чисел.

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

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	5 5	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	94	9 4	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, иначе сортировка заканчивается.