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

Сортировка

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

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

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

Этот метод обычно заключается в следующем. Элементы условно разделяются на готовую последовательность а_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

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

 

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