Лабораторная работа № 9. Тема: “Внутренняя сортировка”

Тема: “Внутренняя сортировка”.

Цель работы: освоить методы сортировки элементов одномерных массивов памяти ПЭВМ, организацию программ по обработке массивов, средства BORLAND PASCAL для работы с файлами.

Краткое теоретическое введение

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

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность а₁,...,a_i-1 и входную последовательность a_i,..., a_n. На каждом шаге, начиная с i=2 и увеличивая i на 1, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы «просеивать» х, сравнивая его с очередным элементом ai и либо вставляя х, либо пересылая ai направо и продвигаясь налево. Заметим, что просеивание может закончиться при двух различных условиях:

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

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

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

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