Сортировка с разделением

После того как мы обсудили два усовершенствованных метода сортировки, основанных на принципах включения и выбора, мы введем третий, улучшенный метод, основанный на принципе обмена. Учитывая, что сортировка методом пузырька в среднем была наименее эффективной из трех алгоритмов простой сортировки, мы должны требовать значительного улучшения, однако неожиданно оказывается, что усовершенствование сортировки, основанной на обмене, которое мы здесь будем обсуждать, дает вообще лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель К. Хоор назвал его быстрой сортировкой.

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены на больших расстояниях. Предположим, что нам даны n элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего n/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться с двух концов к середине. Но все же пример наводит на некоторые мысли.

Попробуем рассмотреть следующий алгоритм: выберем случайным образом какой-то элемент (назовем его x), просмотрим массив, двигаясь слева направо, пока не найдем элемент ai > x. Затем просмотрим его справа налево, пока не найдем элемент ai < x. Теперь поменяем местами два элемента и продолжим процесс «просмотра с обменом», пока два элемента не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими, чем x,и правую - с ключами большими x.

Этот алгоритм очень прост и эффективен, так как основные величины, участвующие в сравнениях: i, j и x, можно во время просмотра хранить на быстрых регистрах. Но он также может быть весьма неуклюжим, как видно из примера с n одинаковыми ключами, в котором выполняется n/2 обменов. Эти ненужные обмены можно легко устранить, заменив операторы просмотра на

while a[i].key £ x.key do i:= i+1;

while x.key £ a[j].key do j:= j -1;

Но тогда выбранный для сравнения элемент x, который находится в массиве, перестанет служить в качестве барьера для двух разнонаправленных просмотров. В случае, когда в массиве все ключи одинаковы, просмотры выйдут за его границы, если не использовать более сложные условия окончания. Простота условий оправдывает излишние обмены, которые в среднем для «случайных» массивов происходят довольно редко. Небольшую экономию можно, однако, получить, если заменить условие, управляющее обменом, на i<j вместо i£j. Но такую замену нельзя распространить на оба оператора (i:=i+1;j:=j-1), которые поэтому требуют использования различных условий. Необходимость условия i£j можно проиллюстрировать следующим примером при x=2: 1 1 1 2 1 1 1

Первый просмотр и обмен дают 1 1 1 1 1 1 2, причем i=5, j=6. Второй просмотр не изменяет массив и заканчивается с i=7 и j=6. Если бы обмен не подчинялся условию i £ j, то произошел бы ошибочный обмен а₆ и а₇.

В правильности алгоритма разделения можно убедиться на основании того, что оба утверждения (1.2) являются вариантами оператора цикла с постусловием. В начале, при i=1 и j=n, они, очевидно, истинны, а при выходе с i>j они предполагают, что получен нужный результат.

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

Процедура рекурсивно вызывает сама себя. Такое использование рекурсии в алгоритмах - очень мощное средство. В некоторых языках программирования старого образца рекурсия по некоторым техническим причинам запрещена. Сейчас мы покажем, как можно выразить тот же алгоритм в виде не рекурсивной процедуры. Очевидно, что при этом рекурсия представляется как итерация, причем необходимы некоторые дополнительные операции для хранения информации.

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

Задание к работе:

Составить блок-схему и программу на языке BORLAND PASCAL, которая:

- формирует на магнитном диске файл целых, вещественных, строковых переменных или текстовый файл (по указанию преподавателя);

- копирует содержимое файла в память;

- сортирует массив в памяти тремя способами: двумя простыми (методы выбора, вставки или обмена) и двумя усовершенствованными (сложными) по выбору. Методы выбрать самостоятельно.

Программу оформить с заставкой, оформленной в виде процедуры. Индикация содержимого файла, вывод отсортированных массивов после каждого метода, вывод отсортированного массива в файл (после сортировки каждым методом с уникальным именем).

Во время работы по сортировке необходимо индицировать на экране время, затраченное на каждый из методов, для чего использовать стандартную процедуру GETTIME запроса текущего времени в ОС.

Предпочтительней использование динамических переменных.

Программу оформить в соответствие с требованиями: комментарии (заглавный и строчные), модульный принцип (все - в виде процедур и функций).

Содержание отчета: титульный лист, тема и цель работы, № варианта задания и собственно задание, постановка задачи и сущность методов сортировки массивов, блок-схема алгоритма, текст программы, результаты работы программы, выводы.

Контрольные вопросы

1. Объясните принцип работы с файлами в Borland Pascal.

2. Сущность метода выбора сортировки одномерного массива.

3. Сущность метода вставки сортировки одномерного массива.

4. Сущность метода пузырька сортировки одномерного массива.

5. Какие Вы знаете сложные методы сортировки?

6. Охарактеризуйте интерфейс процедуры GETTIME.