ПРИМЕЧАНИЕ

Существует более простая реализация метода быстрой сортировки, основанная на рекурсии. Мы рассмотрим ее на седьмом семинаре.

 

В приведенной ниже программе стек реализуется в виде двух массивов stackr и stackl и одной переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива). Для этого алгоритма количество элементов в стеке не может превышать n, поэтому размер массивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке — уменьшается. Про данный способ реализации стека рассказывается в Учебнике на с. 126.

 

Ниже приведена программа, реализующая этот алгоритм.

 

#include < iostream.h> #include < conio.h> int main () { const int n = 20; float arr[n], middle, temp; int *stackl = new int [n], *stackr = new int [n], sp = 0; int i, j, left, right; cout < < " Введите элементы массива: "; for (i = 0; i < n; i++) cin > > arr[i]; // сортировка sp = 1; stackl[1] = 0; staclr [1] =n – 1; // 1 while (sp > 0) { // 2 // выборка из стека последнего запроса left = stackl[sp]; // 3 right = stack[sp]; // 4 sp--; // 5 while (left < right) { // 6 // разделение { arr[left].. arr[right]} i = left; j = right; // 7 middle = arr[(left + right) / 2]; // 8 while (i < j); // 9 while (arr[i] < middle) i++; // 10 while (middle < arr[j]) j--; // 11 if (i < = j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if (i < right) { // 12 // запись в стек запроса из правой части sp++; stackl[sp] = i; stackr[sp] = right; } right = j; // 13 // теперь left и right ограничивают левую часть } } // вывод резултьата for (i = 0; i < n; i++) cout < < arr[i] < < ' '; cout < < endl; return 0; }

 

На каждом шаге сортируется один фрагмент массива. Левая граница фрагмент хранится в переменной left, правая — в переменной right. Сначала фрагмент устанавливается размером с массив целиком (строка 1). В операторе 8 выбирается «средний» элемент фрагмента.

 

Для продвижения по массиву слева направо в цикле 10 используется переменная i справа налево — переменная j (в цикле 11). Их начальные значения устанавливаются в операторе 7. После того, как оба счетчика «сойдутся» где-то в средней части массива, происходит выход из цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые границы левой части для сортировки на следующем шаге.

 

Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла б, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3, 4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.

 

Добавьте в программу подсчет количества итераций основного цикла. Прогоните программу несколько раз для массивов с большим количеством элементов1 и сравните с аналогичной программой, реализующей метод выбора. Сделайте выводы.

 

Метод быстрой сортировки был предложен Ч. Хоаром. Впоследствии дотошный исследователь этого и других методов сортировки Д. Кнут (D. Knuth) установил, что размер стека может быть уменьшен до величины log₂n, если после каждого появления двух частей, подлежащих дальнейшей обработке, более длинную часть откладывать на потом (помещать в стек), а более короткую обрабатывать немедленно. В качестве дополнительного упражнения напишите улучшенную версию программы, в которой реализована эта идея и размер стека уменьшен до log₂n.

 

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

 

Давайте повторим основные моменты этого семинара.

 

1. Размерность не-динамического массива может быть только константой или константным выражением. Рекомендуется задавать размерность с помощью именованной константы.
2. Элементы массивов нумеруются с нуля, поэтому максимальный номер элемента всегда на единицу меньше размерности.
3. Автоматический контроль выхода индекса за границы массива не производится, поэтому программист должен следить за этим самостоятельно.
4. Указатель — это переменная, в которой хранится адрес области памяти.
5. Имя массива является указателем на его нулевой элемент.
6. Обнуления динамической памяти при ее выделении не происходит. Инициализировать динамический массив нельзя.
7. Освобождение памяти, выделенной посредством new[ ], выполняется с помощью операции delete[ ].
8. Перед выходом локального указателя из области его действия необходимо освобождать связанную с ним динамическую память.
9. Если количество элементов, которые должны быть введены в программу, известно до ее выполнения, определяйте массив в операторе описания переменных (причем лучше как локальную переменную, чем как глобальную); если количество можно задать во время выполнения программы, но до ввода элементов, создавайте динамический массив; если нет, используйте линейный список или другую динамическую структуру.
10. Алгоритмы сортировки массивов различаются по быстродействию, занимаемой памяти и области применения.