Быстрая сортировка

Разбить на страницы

Показывать лекцию целиком

Темой настоящей главы является алгоритм сортировки, который, возможно, используется гораздо чаще любых других - алгоритм быстрой сортировки (quicksort). Первоначальный вариант этого алгоритма был изобретен в 1960 г. Ч. Хоаром (C.A.R. Hoare) и с той поры исследовался многими специалистами (см. раздел ссылок). Быстрая сортировка популярна прежде всего потому, что ее нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше ресурсов по сравнению с другими методами сортировки.

Алгоритм быстрой сортировки обладает и другими привлекательными особенностями: он принадлежит к категории обменных сортировок (использует лишь небольшой вспомогательный стек), на упорядочение N элементов в среднем затрачивает время, пропорциональное N log N, и имеет исключительно короткий внутренний цикл. Его недостатком является то, что он неустойчив, выполняет в худшем случае N 2 операций и ненадежен в том смысле, что простая ошибка в реализации может остаться незамеченной, но существенно понизить производительность на некоторых видах файлов.

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

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

Тщательно настроенная версия быстрой сортировки обычно работает быстрее любого другого метода сортировки на большинстве компьютеров, поэтому быстрая сортировка широко используется как библиотечная программа сортировки и в других серьезных приложениях сортировки. Утилита сортировки из стандартной библиотеки С++ называется qsort, т.к. ее различные реализации обычно основаны на алгоритме быстрой сортировки. Однако время выполнения быстрой сортировки зависит от организации входных данных и колеблется между линейной и квадратичной зависимостью от количества сортируемых элементов, и пользователи иногда бывают неприятно удивлены неожиданно неудовлетворительной работой сортировки на некоторых видах входных данных, особенно при использовании хорошо отлаженных версий этого алгоритма. Если приложение работает настолько плохо, что возникает подозрение в наличии дефектов в реализации быстрой сортировки, то более надежным выбором может оказаться сортировка Шелла, хорошо работающая при меньших затратах на реализацию. Однако в случае особо крупных файлов быстрая сортировка обычно выполняется в пять-десять раз быстрее сортировки Шелла, а для некоторых видов файлов, часто встречающихся на практике, ее можно адаптировать для еще большего повышения эффективности.

Базовый алгоритм

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

Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.

Ни один из элементов a[i], ..., a[i-1] не является большим a[i].

Ни один из элементов a[i+1], ..., a[r] не является меньшим a[i].

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

(рис 7.1) Пример работы быстрой сортировки

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

Программа 7.1. Быстрая сортировка

Если массив содержит один или ноль элементов, то ничего делать не надо. Иначе массив обрабатывается процедурой partition (см. программу 7.2), которая помещает на свое место элемент a[i] для некоторого i между l и r включительно и переупорядочивает остальные элементы таким образом, что рекурсивные вызовы этой процедуры завершают сортировку.

template <class Item>
  void quicksort(Item a[], int l, int r)
    {
      if (r <= l) return;
      int i = partition(a, l, r);
      quicksort(a, l, i-1);
      quicksort(a, i+1, r);
    }

Мы будем использовать следующую общую стратегию реализации разбиения. Сначала в качестве центрального элемента (partitioning element) произвольно выбирается элемент a[r] - тот, который будет помещен в окончательную позицию.

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

(рис )

Здесь и рис 7.3.

Внутренний цикл быстрой сортировки увеличивает индекс на единицу и сравнивает элементы массива с постоянной величиной. Именно эта простота и делает быструю сортировку быстрой: трудно представить себе более короткий внутренний цикл в алгоритме сортировки.

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

(рис 7.2) Разбиение при работе быстрой сортировки

Разбиение, выполняемое в процессе быстрой сортировки, начинается с (произвольного) выбора центрального элемента. В программе 7.2 для этого берется самый правый элемент E. Затем слева пропускаются все меньшие элементы, а справа - все большие, выполняется обмен элементов, остановивших просмотр, и т.д. до встречи индексов. Вначале выполняется просмотр массива слева, который останавливается на элементе S, потом выполняется просмотр справа, который останавливается на элементе A, а затем элементы S и A меняются местами. Потом просмотр продолжается: слева - до остановки на элементе O, а справа - на элементе E, после чего O и E меняются местами. После этого индексы просмотра перекрещиваются: просмотр слева останавливается на R, а просмотр справа останавливается на E. Для завершения процесса центральный элемент (левая E) обменивается с R.

Программа 7.2. Разбиение

Переменная v содержит значение центрального элемента a[r], а i и j - соответственно левый и правый индексы просмотра. Цикл разбиения увеличивает i и уменьшает j на 1, соблюдая условие, что ни один элемент слева от i не больше v и ни один элемент справа от j не больше v. После встречи указателей процедура разбиения завершается перестановкой a[r] и a[i], при этом в a[i] заносится значение v, и справа от v не останется меньших его элементов, а слева - больших. Цикл разбиения реализован в виде бесконечного цикла с выходом по break после перекрещивания указателей. Проверка j==1 вставлена на случай, если центральный элемент окажется наименьшим в файле.

template <class Item>
  int partition(Item a[], int l, int r)
    { int i = l-1, j = r; Item v = a[r]; 
      for (;;)
        {
while (a[++i] < v) ;
while (v < a[-j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
        }
        exch(a[i], a[r]);
        return i;
    }

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

Процесс разбиения неустойчив, поскольку во время любой перестановки любой ключ может быть перемещен через большое количество равных ему ключей (еще не проверенных). Простые способы сделать быструю сортировку массива устойчивой пока не известны.

Реализацию процедуры разбиения следует выполнять с особой осторожностью. В частности, наиболее простой способ гарантировать завершение рекурсивной программы заключается в том, чтобы она (1) не вызывала себя для файлов размером 1 или менее и (2) вызывала себя только для файлов, размер которых строго меньше размеров входного файла. Эти правила кажутся очевидными, однако легко упустить из виду такое свойство входных данных, которое повлечет за собой катастрофическую ошибку.

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

При наличии повторяющихся ключей фиксация момента перекрещивания индексов сопряжена с определенными трудностями. Процесс разбиения можно слегка усовершенствовать, заканчивая просмотр при вместо R было E. Это изменение стоит внести в программу, т.к. иначе программа в том виде, в каком она здесь представлена, оставляет запись с ключом, равным центральному, в a[r], что приводит к вырожденному первому разбиению в вызове quicksort(a, i+1, r), поскольку его правый ключ оказывается наименьшим. Однако реализация разбиения в программе 7.2, несколько проще для понимания, так что в дальнейшем мы будем считать ее базовым методом разбиения. Если в файле может быть значительное число повторяющихся ключей, то на передний план выступают другие факторы, которые будут рассмотрены ниже.

Возможны три основных стратегии обработки ключей, равных центральному элементу: останавливать оба индекса на таких ключах (как в программе 7.2); останавливать один индекс, а другим пропустить их при просмотре; или пропустить их обоими индексами. Вопрос о том, какая из этих стратегий лучше, детально изучен математически, и результаты показывают, что лучше останавливать оба индекса - главным образом потому, что эта стратегия лучше балансирует разбиения при наличии большого количества повторяющихся ключей, в то время как две другие для некоторых файлов приводят к плохо сбалансированным разбиениям. В разделе 7.6 мы рассмотрим несколько более сложный и гораздо более эффективный способ работы с повторяющимися ключами.

В конечном счете эффективность сортировки зависит от качества разбиения файла, которое, в свою очередь, зависит от значения центрального элемента.

(рис 7.3) Динамические характеристики разбиения при работе быстрой сортировки

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

На рис 7.2 видно, что разбиение делит большой случайно упорядоченный файл на два меньших случайно упорядоченных файла, но реально точка раздела может оказаться в любом месте файла. Лучше было бы выбирать элемент, который разделит файл близко к середине, однако необходимая для этого информация отсутствует. Если файл случайно упорядочен, то выбор элемента a[r] в качестве центрального эквивалентен выбору любого другого конкретного элемента; и в среднем разбивает файл близко к середине. В разделе 7.4 мы проведем анализ алгоритма, который позволит сравнить этот выбор с идеальным выбором, а в разделе 7.5 увидим, как этот анализ поможет нам при выборе центрального элемента, повышающем эффективность алгоритма.

Упражнения

7.1. Покажите в стиле вышеприведенного примера, как быстрая сортировка сортирует файл E A S Y Q U E S T I O N.

7.2. Покажите, как производится разбиение файла 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0, используя для этой цели программу 7.2 и поправки, предложенные в тексте.

7.3. Реализуйте разбиение без использования операторов break или goto.

7.4. Разработайте устойчивую быструю сортировку для связных списков.

7.5. Какое максимальное количество раз может быть перемещен наибольший элемент во время выполнения быстрой сортировки файла из N элементов?

Характеристики производительности быстрой СОРТИРОВКИ

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

Лемма 7.1. Быстрая сортировка в худшем случае выполняет порядка N²/2 сравнений.

Как только что было показано, количество сравнений, выполняемых при сортировке уже упорядоченного файла, равно

N + (N - 1) + (N - 2) + ... + 2 + 1 = (N + 1) N/ 2.

Все разбиения также являются вырожденными и для обратно упорядоченных файлов, и для других редко встречающихся на практике файлов (см. упражнение 7.6). $$$\blacksquare$$$

Это поведение означает не только то, что время выполнения будет порядка N²/2, но также и то, что объем памяти, требуемой для обслуживания рекурсии, будет порядка N (см. раздел 7.3), что неприемлемо для больших файлов. К счастью, существуют сравнительно простые способы резко уменьшить вероятность того, что этот наихудший случай встретится в типичных применениях программы.

Наилучшим для быстрой сортировки является случай, когда на каждой стадии разбиения файл делится точно пополам. Тогда количество операций сравнения, выполняемых быстрой сортировкой, удовлетворяет рекуррентному соотношению типа " разделяй и властвуй " .

C_N = 2C_N/2 + N

Член 2C_N/2 соответствует затратам на сортировку двух подфайлов, а N соответствует затратам на проверку каждого элемента при использовании того или другого индекса разбиения. Мы уже знаем из , что это рекуррентное уравнение имеет решение $$$$C_{N}\approx NlgN$$$$

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

Лемма 7.2. Быстрая сортировка в среднем выполняет порядка 2NlnN сравнений. Точная рекуррентная формула для количества сравнений, выполняемых во время быстрой сортировки N случайно распределенных различных элементов, имеет вид $$$$C_{N}=N+1+\dfrac{1}{N}\sum \limits_{1\leq k\leq N} (C_{k-1}+C_{N-k}) {\ для\ }N\geq 2$$$$

при С₁ = С₀ = 0. Член N + 1 учитывает затраты на выполнение операций сравнения центрального элемента с каждым из остальных (и еще двумя, когда индексы пересекаются); остальное следует из того факта, что каждый элемент k может быть центральным с вероятностью 1/k, после чего остаются случайно упорядоченные файлы с размерами k - 1 и N- k.

Это рекуррентное уравнение, хоть и выглядит сложным, на самом деле решается легко, в три шага. Во-первых, С₀ + С₁ + ... + C_N-1 равно C_N-1 + C_N-2 + ... + С₀, следовательно, $$$$C_{N}=N+1+\dfrac{2}{N}\sum \limits_{1\leq k\leq N}C_{k-1}$$$$

Во-вторых, можно избавиться от суммы, умножив обе части равенства на N и вычтя эту же формулу для N- 1:

NC_N - (N - 1)C_N-1 = N (N + 1) - (N - 1)N + 2C_N-1 .

Эта формула упрощается до рекуррентного соотношения

NC_N = (N + 1)C_N-1 + 2N.

В третьих, разделив обе части на N (N + 1), получим соотношение, которое далее сворачивается:

$$ \begin{align*} \dfrac{C_{N}}{N+1}=\dfrac{C_{N-1}}{N}+\dfrac{2}{N+1}\\ =\dfrac{C_{N-2}}{N-1}+\dfrac{2}{N}+\dfrac{2}{N+1}\\ =\vdots\\ =\dfrac{C_{2}}{3}+\sum \limits_{3\leq k\leq N}\dfrac{2}{k+1} \end{align*} $$

Этот точный ответ почти равен сумме, легко аппроксимируемой интегралом (см. раздел 2.3 ): $$$$\dfrac{C_{N}}{N+1}\approx 2\sum \limits_{1\leq k\leq N}\dfrac{1}{k}\approx 2\int\limits_{1}\limits^{N}\dfrac{1}{x}dx=2\ln{N}$$$$

откуда и вытекает нужный результат. Обратите внимание, что $$$2N lnN \approx 1,39N lgN$$$, так что среднее количество операций сравнения приблизительно лишь примерно на 39% больше, чем в лучшем случае. $$$\blacksquare$$$

Данный анализ предполагает, что сортируемый файл содержит случайно упорядоченные записи с различными ключами, однако, как показано на рис 7.4, реализации в программах 7.1 и 7.2 могут работать медленно в тех случаях, когда ключи не обязательно различны и не обязательно расположены в случайном порядке (рис 7.4). Если программа сортировки будет использоваться многократно или будет применяться для очень большого файла (или, в особенности, если она должна использоваться как стандартная библиотечная сортировка, которая будет применяться для сортировки файлов с неизвестными характеристиками), тогда следует рассмотреть несколько усовершенствований, предлагаемых в разделах 7.5 и 7.6, которые значительно уменьшают вероятность появления на практике неудачных случаев, а также уменьшают среднее время выполнения сортировки примерно на 20%.

(рис 7.4) Динамические характеристики быстрой сортировки при обработке различных видов файлов

Выбор произвольного центрального элемента в быстрой сортировке приводит к различным вариантам разбиения для различных файлов. На данных диаграммах приведены начальные части процессов разбиения для случайного файла с равномерным распределением, случайного файла с нормальным распределением, почти упорядоченного файла, почти упорядоченного по убыванию и случайно упорядоченного с 10 различными значениями ключей (слева направо). Используется относительное большое значение отсечения для подфайлов небольшого размера. Элементы, не задействованные в разбиении, оказываются расположенными близко к диагонали, и остается массив, который легко упорядочить сортировкой вставками. Для почти упорядоченных файлов требуется очень большое количество разбиений.

Упражнения

7.6. Приведите шесть файлов из 10 элементов, для которых быстрая сортировка (программа 7.1) выполняет такое же количество сравнений, что и в худшем случае (когда все элементы упорядочены).

7.7. Напишите программу для расчета точного значения C_N и сравните это точное значение с аппроксимацией 2N lnN для N = 10³, 10⁴, 10⁵ и 106.

7.8. Сколько примерно операций сравнения выполнит быстрая сортировка (программа 7.1) при сортировке файла из N одинаковых элементов?

7.9. Сколько примерно операций сравнения выполнит быстрая сортировка (программа 7.1) при сортировке файла, состоящего из N элементов, ключи которых могут иметь только два различных значения (к элементов с одним значением и N- к элементов с другим)?

7.10. Напишите программу, генерирующую файл, наилучший для быстрой сортировки, т.е. такой файл из N различных элементов, что каждое его разбиение порождает подфайлы, отличающиеся по размеру не более чем на 1.

Размер стека

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

Для случайно упорядоченных файлов максимальный раздел стека пропорционален log N (см. раздел ссылок), но в вырожденных случаях стек может вырасти до размера, пропорционального N, что показано на рис 7.5. Ведь наихудший случай - это когда входной файл уже отсортирован. Потенциальная возможность роста стека до размера, пропорционального размеру входного файла представляет собой не очевидную, но вполне реальную проблему для рекурсивной реализации быстрой сортировки: стек, пусть и неявно, используется всегда, а вырожденный файл большого размера может стать причиной аварийного завершения программы из-за нехватки памяти. Конечно, для библиотечной программы сортировки такое поведение недопустимо. (На самом деле программе скорее не хватит времени, чем памяти.)

(рис 7.5) Размер стека при работе быстрой сортировки

Рекурсивный стек для быстрой сортировки не бывает большим при обработке случайно упорядоченных файлов, но в вырожденных случаях он может занимать очень большой объем памяти. Здесь приведены графики размеров стека для двух случайно упорядоченных файлов (слева и в центре) и для частично упорядоченного файла (справа).

Трудно гарантированно исключить такое поведение программы, но в разделе 7.5 мы увидим, что несложно предусмотреть специальные средства, которые сведут вероятность возникновения таких вырожденных случаев почти к нулю.

Программа 7.3 представляет собой нерекурсивную реализацию, которая решает эту проблему, проверяя размеры обоих подфайлов и первым помещая в стек больший из них. На рис 7.6 показана эта стратегия. Сравнивая данный пример с приведенным на рис 7.1, мы видим, что это правило не изменяет подфайлы, меняется лишь порядок их обработки. Так что мы экономим память без изменения времени выполнения.

Программа 7.3. Нерекурсивная быстрая сортировка

Данная нерекурсивная реализация (см. ) быстрой сортировки использует явный стек магазинного типа, заменяя рекурсивные вызовы помещением в стек параметров, а рекурсивные вызовы процедур и выходы из них - циклом, выталкивающим параметры из стека и обрабатывающим их, пока стек не пуст. Больший из двух подфайлов помещается в стек первым, чтобы максимальная глубина стека при сортировке N элементов не превосходила lgN (см. свойство 7.3).

  #include "STACK.cxx"
  inline void push2(STACK<int> s, int A, int B)
    { s.push(B); s.push(A); }
template <class Item>
  void quicksort(Item a[], int l, int r)
    { STACK<int> s(50)); push2(s, l, r);
      while (!s.empty())
        {
l = s.pop(); r = s.pop();
if (r <= l) continue;
int i = partition(a, l, r);
if (i-1 > r-i)
  { push2(s, l, i-1); push2(s, i+1, r); }
else
  { push2(s, i+1, r); push2(s, l, i-1); }
        }
    }

(рис 7.6) Пример работы быстрой сортировки (вначале упорядочивается меньший подфайл)

Порядок обработки подфайлов не влияет ни на корректность работы алгоритма быстрой сортировки, ни на время выполнения, однако он может повлиять на размер стека, необходимого для поддержки рекурсивной структуры. Здесь после каждого разбиения вначале обрабатывается меньший из двух подфайлов.

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

Лемма 7.3. Если при быстрой сортировке файла из N элементов меньший из двух подфайлов сортируется первым, то размер стека никогда не превышает lgN элементов.

В худшем случае размер стека должен быть меньше TN, где TN удовлетворяет рекуррентному соотношению $$$T_{N}=T_{\lfloor{N/2}\rfloor}+1$$$ при T₁ = T₀ = 0. Это стандартное соотношение из рассмотренных в (см. упражнение 7.13). $$$\blacksquare$$$

(рис 7.7) Дерево разбиений быстрой сортировки

Если свернуть диаграммы разбиений на рис 7.1 и рис 7.6, соединив каждый центральный элемент с центральными элементами из двух его подфайлов, то получится такое статическое представление процесса разбиения (в обоих случаях). В данном бинарном дереве каждый подфайл представлен своим центральным элементом (или целиком подфайлом, если его размер равен 1), а поддеревья каждого узла представляют подфайлы после их разбиения. Чтобы не загромождать рисунок, пустые подфайлы здесь не показаны, хотя наши рекурсивные версии алгоритма выполняют рекурсивные вызовы при r < l, т.е. когда центральный элемент является наименьшим или наибольшим в файле. Вид дерева не зависит от порядка разбиения подфайлов. Наша рекурсивная реализация быстрой сортировки соответствует посещению узлов дерева в прямом порядке, а нерекурсивная реализация соответствует правилу посещения вначале меньшего поддерева.

Этот метод не обязательно будет работать в настоящей рекурсивной реализации, поскольку он зависит от освобождения стека перед выходом или после выхода (end-или tail-recursion removal). Если последним действием какой-либо процедуры является вызов другой процедуры, то некоторые системы программирования удаляют локальные переменные из стека до вызова, а не после. Без освобождения стека перед выходом невозможно гарантировать, что размер стека, используемого быстрой сортировкой, будет мал. Например, вызов быстрой сортировки для уже отсортированного файла размером N породит рекурсивный вызов для такого же файла, но размером N - 1, который, в свою очередь, породит рекурсивный вызов для файла размером N - 2 и т.д., и наконец нарастит глубину стека пропорционально N. Это наблюдение подталкивает к использованию нерекурсивной реализации, не допускающей чрезмерный рост стека. C другой стороны, некоторые компиляторы C++ автоматически вставляют освобождение стека перед выходом, и многие машины имеют аппаратную поддержку вызовов функций - поэтому в таких средах нерекурсивная реализация из программы 7.3 может оказаться более медленной, чем рекурсивная реализация из программы 7.1.

На рис 7.7 еще раз проиллюстрирован тот факт, что для любого файла нерекурсивный метод обрабатывает те же подфайлы (но в другом порядке), что и рекурсивный метод. На нем показана древовидная структура с центральным элементом в корне и его левым и правым поддеревьями, соответствующими левому и правому подфайлам. Использование рекурсивной реализации быстрой сортировки соответствует обходу этих узлов в прямом порядке; нерекурсивная реализация соответствует правилу просмотра сначала наименьшего поддерева.

При явном использовании стека, как в программе 7.3, удается избежать некоторых затрат, присущих рекурсивной реализации, хотя современные системы программирования обеспечивают минимум затрат для таких простых программ. Программа 7.3 может быть еще улучшена. Например, она помещает в стек оба подфайла только для того, чтобы тут же вытолкнуть верхний из них; можно улучшить ее, присваивая значения переменным l и r напрямую. Далее, проверка $$$r\leq l$$$ выполняется после выталкивания подфайлов из стека, тогда как эффективнее вообще не помещать такие файлы в стек (см. упражнение 7.14). Может показаться, что это не важно, однако рекурсивный характер быстрой сортировки на самом деле приводит к тому, что значительная часть подфайлов в процессе сортировки имеет размеры 0 или 1. Ниже мы рассмотрим важное усовершенствование быстрой сортировки, которое использует эту идею - обрабатывать все подфайлы небольшого размера максимально экономично - для увеличения ее эффективности.

Упражнения

7.11. В стиле рис 5.5 приведите содержимое стека после каждой пары операций поместить в стек и вытолкнуть из стека, если программа 7.3 используется для сортировки файла с ключами E A S Y Q U E S T I O N.

7.12. Выполните упражнение 7.11 для случая, когда в стек всегда сначала помещается правый подфайл, а затем левый подфайл (как это принято в рекурсивной реализации).

7.13. Завершите доказательство по индукции леммы 7.3.

7.14. Внесите в программу 7.3 такие изменения, чтобы она никогда не помещала в стек подфайлы с $$$r\leq l$$$ .

7.15. Приведите максимальный размер стека, требуемый программой 7.3 при N = 2ⁿ.

7.16. Приведите максимальные размеры стека, требуемые программой 7.3 при N = 2ⁿ - 1 и N = 2ⁿ + 1.

7.17. Стоит ли для нерекурсивной реализации быстрой сортировки использовать вместо стека очередь? Обоснуйте ваш ответ.

7.18. Определите, выполняется ли в вашей системе программирования освобождение стека перед выходом.

7.19. Определите эмпирическим путем средний размер стека, используемого базовым рекурсивным алгоритмом быстрой сортировки для случайно упорядоченных файлов из N элементов, для N = 10³, 10⁴, 10⁵ и 10⁶.

7.20. Определите среднее количество подфайлов размера 0, 1 и 2, если быстрая сортировка используется для сортировки случайно упорядоченного файла из N элементов.

Подфайлы небольшого размера

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

  if (r-1 <= M) insertion(a, l, r);

Здесь M - некоторый параметр, точное значение которого зависит от реализации. Оптимальное значение M можно определить либо аналитически, либо эмпирическими исследованиями. Обычно такие исследования показывают, что время выполнения мало изменяется для M в диапазоне примерно от 5 до 25, при этом оно процентов на 10 меньше, чем для элементарного выбора M = 1 (см. рис.7.8).

(рис 7.8) Отсечение небольших подфайлов

Выбор оптимального значения для размера отсекаемых небольших подфайлов дает в среднем примерно 10-процентное снижение времени выполнения. Выбор точного значения не критичен, т.к. примерно одинаковый выигрыш дают значения из широкого диапазона (примерно от 5 до 20). Жирная линия (вверху) получена экспериментально, а тонкая (внизу) выведена аналитически.

Несколько более простой и чуть более эффективный по сравнению с сортировкой вставками способ обработки небольших подфайлов состоит в замене проверки в начале программы на

  if ( r-1 <= M) return;

То есть при разбиении небольшие подфайлы просто игнорируются. В нерекурсивной реализации это можно сделать, не помещая в стек все файлы с размером, меньшим M, либо игнорируя все такие файлы, обнаруженные в стеке. По окончании разбиения получается почти отсортированный файл. Как отмечалось в разделе 6.5 , для таких файлов наилучшим методом является сортировка вставками. То есть сортировка вставками работает с таким файлом примерно так же хорошо, как и с набором небольших файлов, которые получаются при непосредственном ее применении. Этот метод следует применять осторожно, т.к. сортировке вставками придется работать, даже если алгоритм быстрой сортировки содержит фатальную ошибку, из-за которой она просто не сможет работать. Единственным признаком, что что-то не так, может быть значительное увеличение времени сортировки.

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

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

(рис 7.9) Сравнения в быстрой сортировке

Подфайлы обрабатываются в быстрой сортировке независимо. На этом рисунке показан результат разбиения каждого подфайла при сортировке 200 элементов с отсечением файлов размером 15 и меньше. Грубую оценку количества сравнений можно получить, подсчитав количество отмеченных элементов в вертикальных столбцах. В данном случае каждая позиция массива участвует на протяжении сортировки лишь в шести или семи подмассивах.

Упражнения

7.21. Нужны ли сигнальные ключи, если сортировка вставками вызывается непосредственно из быстрой сортировки?

7.22. Измените программу 7.1 так, чтобы можно было подсчитать процент операций сравнения, используемых при разбиении файлов размером меньше 10, 100 и 1000. Напечатайте эти проценты для сортировки случайно упорядоченных файлов из N элементов для N = 10³, 10⁴, 10⁵ и 10⁶.

7.23. Реализуйте рекурсивный вариант быстрой сортировки с отсечением для сортировки вставками подфайлов с менее чем M элементами. Эмпирически определите значение M, при котором программа 7.4 на вашей вычислительной системе достигает максимального быстродействия при сортировке случайно упорядоченных файлов из N элементов для N = 10³, 10⁴, 10⁵ и 10⁶.

7.24. Выполните упражнение 7.23, используя нерекурсивную реализацию.

7.25. Выполните упражнение 7.23, для случая, когда сортируемые записи содержат ключ и b указателей на другую информацию (но не используя сортировку указателей).

7.26. Напишите программу, выводящую гистограмму (см. программу 3.7) размеров подфайлов, передаваемых сортировке вставками, при выполнении быстрой сортировки файла размером N с отсечением подфайлов с размерами, меньшими M. Выполните эту программу для M = 10, 100 и 1000 и N = 10³, 10⁴, 10⁵ и 10⁶.

7.27. Определите эмпирическим путем средний размер стека, используемого быстрой сортировкой с отсечением подфайлов размера M, для сортировки случайно упорядоченных файлов из Nэлементов, при M = 10, 100 и 1000 и N =10³, 10⁴, 10⁵ и 10⁶.

Разбиение по медиане из трех

Другим усовершенствованием быстрой сортировки является использование центрального элемента, который с большей вероятностью делит файл близко к середине. Есть несколько возможностей сделать это. Достаточно надежный способ избежать худшего случая состоит в использовании случайного элемента массива в качестве центрального. Тогда вероятность наихудшего выбора пренебрежимо мала. Этот метод является простым примером вероятностного алгоритма (probabilistic algorithm) - алгоритма, который использует случайный выбор для достижения хорошей производительности с высокой вероятностью, независимо от упорядоченности входных данных. Далее в этой книге мы увидим многочисленные примеры использования случайного выбора при разработке алгоритмов, особенно если возможна регулярность входных данных. На практике использование генератора случайных чисел для быстрой сортировки может оказаться излишним: достаточно эффективен простой произвольный выбор.

Другой распространенный способ определения лучшего центрального элемента заключается в выборке трех элементов из файла и использовании в качестве центрального элемента их медианы. Если выбрать за эти три элемента левый, правый и средний элементы массива, то заодно можно включить в схему и сигнальные элементы: сортируем три выбранных элемента (используя метод трех обменов, описанный в ), потом обмениваем средний из них с элементом a[r-1], и затем выполняем алгоритм разбиения для a[l+1], ..., a[r-2]. Это усовершенствование называется методом медианы из трех (median-of-three).

Метод медианы из трех повышает эффективность сортировки тремя способами. Во-первых, он существенно снижает вероятность появления наихудшего случая при сортировке любого реального файла. Чтобы сортировка выполнилась за время порядка N², два из трех выбранных элементов должны быть наибольшими или наименьшими элементами в файле, и это событие должно постоянно повторяться для большинства разбиений. Во-вторых, он устраняет необходимость в сигнальном элементе, т.к. эту функцию берет на себя один из трех элементов, проверенных перед разбиением. В-третьих, он уменьшает общее среднее время выполнения алгоритма примерно на 5%.

Сочетание метода медианы из трех с отсечением небольших подфайлов может улучшить время выполнения быстрой сортировки по сравнению с элементарной рекурсивной реализацией на 20-25%. Программа 7.4 представляет собой реализацию, вобравшую в себя все эти усовершенствования.

Можно было бы продолжить усовершенствование программы, удалив рекурсию, заменив вызовы подпрограмм непосредственной вставкой их кода, используя сигнальные значения и т.п. Однако в современных машинах такие вызовы процедур вполне эффективны, и они находятся вне внутреннего цикла. Более важно то, что применение отсечения небольших подфайлов компенсирует возможные дополнительные затраты (вне внутреннего цикла). Основной причиной использования нерекурсивной реализации с явным стеком является гарантированное ограничение размера стека (см. рис 7.10).

(рис 7.10) Размер стека для усовершенствованного варианта быстрой сортировки

Сортировка вначале меньшего подфайла гарантирует, что даже в худшем случае размер стека будет логарифмически зависеть от размера файла. Здесь приведены графики размеров стека для тех же файлов, что и на рис 7.5, но при сортировке вначале меньшего подфайла (слева) и с добавлением модификации медианы из трех (справа). Эти диаграммы никак не связаны с временем выполнения, которое зависит скорее от объема файлов в стеке, чем от их количества. Например, для третьего (частично упорядоченного) файла не нужен большой стек, однако сортировка выполняется медленно, т.к. обрабатываемые подфайлы обычно имеют большой размер.

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

Программа 7.4. Усовершенствованная быстрая сортировка

Выбор медианы из первого, среднего и последнего элементов в качестве центрального элемента и отсечение рекурсии для небольших подфайлов может значительно повысить производительность быстрой сортировки. Данная реализация осуществляет разбиение по медиане из первого, среднего и последнего элементов массива (и иначе не включает их в процесс разбиения). Файлы длиной 11 и меньше игнорируются при разбиениях, а затем для завершения сортировки используется метод insertion из .

  static const int M = 10;
  template <class Item>
  void quidcksort(Item a[], int l, int r)
    {
      if (r-1 <= M) return;
      exch(a[(l+r)/2], a[r-1]);
      comexch(a[l], a[r-1]);
      comexch(a[l], a[r]);
      comexch(a[r-1], a[r]);
      int i = partition(a, l+1, r-1);
      quicksort(a,l, i-1);
      quicksort(a, i+1, r);
    }
  template <class Item>
  void hybridsort(Item a[], int l, int r)
    { quicksort(a, l, r); insertion(a, l, r); }

Для случайно упорядоченных файлов первая перестановка в программе 7.4 не нужна. Она оставлена потому, что приводит к оптимальному разбиению уже упорядоченных файлов, а также потому, что служит защитой от нештатных ситуаций, которые могут встретиться на практике (см., например, упражнение 7.33). На рис 7.11 иллюстрируется эффективность использования среднего элемента при определении места разбиения для файлов с различным начальным распределением ключей.

(рис 7.11) Динамические характеристики быстрой сортировки с выбором медианы из трех для различных видов файлов

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

Метод медианы из трех представляет собой специальный случай общего принципа: можно случайным образом выбрать записи из неизвестного файла и использовать свойства этой выборки для оценки свойств всего файла. В случае быстрой сортировки для получения сбалансированного разбиения нужно оценить медиану случайной выборки. Алгоритм таков, что нам не нужна очень точная оценка (или оценка вообще не нужна, если она требует больших вычислительных затрат); мы лишь хотим избежать очень неудачной оценки. Если для оценки используется случайная выборка лишь из одного элемента, получается вероятностный алгоритм, который почти наверняка выполняется быстро, независимо от входных данных. Если случайно выбрать из файла три или пять элементов, и затем использовать для разбиения их медиану, получится лучшее разбиение, но это усовершенствование будет достигнуто ценой выполнения и оценки выборки.

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

На больших случайно упорядоченных файлах быстрая сортировка (программа 7.1) работает почти в три раза быстрее, чем сортировка Шелла (программа 6.6). Отсечение небольших подфайлов и разбиение по медиане из трех (программа 7.4) еще более сокращают время сортировки.

Эмпирическое сравнение алгоритмов быстрой сортировки
N	Шелла	Базовая быстрая сортировка			Быстрая сортировка с разбиением по медиане из трех
N	Шелла	`M = 0`	`M = 10`	`M = 20`	`M = 0`	`M = 10`	`M = 20`
12500	6	2	2	2	3	2	3
25000	10	5	5	5	5	4	6
50000	26	11	10	10	12	9	14
100000	58	24	22	22	25	20	28
200000	126	53	48	50	52	44	54
400000	278	116	105	110	114	97	118
800000	616	255	231	241	252	213	258

Упражнения

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

7.29. Реализуйте быструю сортировку, основанную на разбиении по медиане случайной выборки из пяти элементов файла. Элементы выборки не должны принимать участия в разбиении (см. упражнение 7.28). Сравните производительность полученного алгоритма с методом медианы из трех для больших случайно упорядоченных файлов.

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

7.31. Реализуйте быструю сортировку с использованием случайной выборки из 2^k - 1

элементов. Сначала отсортируйте выборку, затем рекурсивной программой разбейте файл по медиане выборки, а оставшиеся половины выборки поместите в каждый подфайл так, чтобы они использовались в этих подфайлах без дальнейшей сортировки. Такой метод сортировки называется сортировкой методом случайной выборки (samplesort).

7.32. Определите эмпирическим путем наилучший размер выборки для сортировки

методом случайной выборки (см. упражнение 7.31) для N = 10³, 10⁴, 10⁵ и 10⁶. Имеет ли значение, какой вид сортировки используется для упорядочения самой выборки: быстрая сортировка или сортировка методом случайной выборки?

7.33. Покажите, что если в программе 7.4 убрать первую перестановку и пропускать ключи, равные центральному, то время ее выполнения для обратно упорядоченных файлов будет квадратичным.

Повторяющиеся ключи

Файлы с большим количеством повторяющихся ключей довольно часто встречаются в различных приложениях. Например, может потребоваться сортировка большого файла с персональными данными по году рождения или даже сортировка для разделения персонала на женщин и мужчин.

Если в сортируемом файле имеется много повторяющихся ключей, рассмотренные нами реализации быстрой сортировки не снижают производительность до неприемлемо низкого уровня, но все же их можно существенно улучшить. Например, файл, который состоит только из одинаковых ключей (одно и то же значение), вообще не нуждается в дальнейшей сортировке, однако наши реализации будут разбивать его до мелких подфайлов, вне зависимости от размера файла (см. упражнение 7.8). Если во входном файле присутствует большое количество повторяющихся ключей, быстрая сортировка, в силу своей рекурсивной природы, обязательно породит много подфайлов, содержащих элементы с одним и тем же ключом, так что здесь имеется возможность для значительного усовершенствования алгоритма.

Идея, которая первой приходит на ум, заключается в разбиении файла на три части, по одной для ключей, меньших, равных и больших центрального элемента:

Выполнение такого разбиения сложнее, чем разбиение на две части, которым мы пользовались ранее. Для решения этой задачи было предложено множество различных методов. Это классическое упражнение по программированию, известное благодаря Дейкстре (Dijkstra) как задача о национальном флаге Дании (Dutch National Flag problem), т.к. трем возможным категориям ключей можно поставить в соответствие три цвета этого флага (см. раздел ссылок). Для быстрой сортировки мы добавим еще одно ограничение: вся работа должна быть выполнена за один проход по файлу - алгоритм, использующий два прохода по данным, замедлит быструю сортировку вдвое, даже если в файле вообще нет повторяющихся ключей.

Интересный метод трехчастного разбиения (three-way partitioning) был предложен в 1993 году Бентли и Макилроем (Bentley and McIlroy). Он представляет собой следующую модификацию стандартной схемы разбиения: помещаем ключи из левого подфай-ла, равные центральному элементу, в левый конец файла, а ключи из правого подфайла, равные центральному элементу - в правый конец файла. Во время процесса разбиения постоянно поддерживается следующая ситуация:

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

(рис 7.12) Трехчастное разбиение

На этой диаграмме показан процесс помещения в окончательные позиции всех ключей, равных центральному элементу. Как и на рис 7.2, выполняется просмотр с левого конца, пока не будет найден ключ, не меньший центрального, и с правого конца, пока не будет найден ключ, не больший центрального, а затем эти элементы обмениваются. Если после обмена левый элемент равен центральному элементу, он обменивается с элементом на левом конце массива; аналогично и справа. После перекрещивания индексов центральный элемент помещается на свое место как и раньше (предпоследняя строка), а затем выполняется обмен всех ключей, равных ему, чтобы они заняли свои места с любой стороны от центрального элемента (нижняя строка).

На рис 7.12 показана работа алгоритма трехчастного разбиения на демонстрационном файле, а программа 7.5 является реализацией быстрой сортировки, основанной на описанном методе. Эта реализация требует добавления всего лишь двух операторов if в цикле перестановки и двух циклов for для завершения разбиения, т.е. перемещения ключей, равных центральному элементу, в окончательные позиции. Похоже, что этот метод трехчастного разбиения требует меньшего кода, чем другие альтернативы. И более того, он не только максимально эффективно обрабатывает повторяющиеся ключи, но и минимизирует издержки в случае, когда повторяющихся ключей нет.

Программа 7.5. Быстрая сортировка с трехчастным разбиением

В основу программы положено разбиение массива на три части: на элементы, меньшие центрального элемента (в a[1], ..., a[j]), элементы, равные центральному элементу (в a[j+1], ..., a[i-1]), и элементы, большие центрального элемента (в a[i], ..., a[r]). После этого сортировка завершается двумя рекурсивными вызовами.

Для достижения этой цели программа хранит ключи, равные центральному элементу, слева между позициями l и p и справа между q и r. В цикле разбиения, после остановки индексов просмотра и перестановки элементов в позициях i и j , выполняется проверка каждого из этих элементов на равенство центральному. Если левый из них равен центральному элементу, он переставляется в левую часть массива; если правый из них равен центральному элементу, он переставляется в правую часть массива.

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

  template <class Item>
  int operator==(const Item A, const Item B)
    { return !less(A, B)  !less(B, A); }
  template <class Item>
  void quicksort(Item a[], int l, int r)
    { int k; Item v = a[r];
      if (r <= l) return;
      int i = l-1, j = r, p = l-1, q = r;
      for (;;)
        {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i],a[j]);
if (a[i] == v) { p++; exch(a[p],a[i]); }
if (v == a[j]) { q-; exch(a[q],a[j]); }
       }
     exch(a[i], a[r]); j = i-1; i = i+1;
     for (k = l ; k <= p; k++, j -) exch(a[k],a[j]);
     for (k = r-1; k >= q; k--, i++) exch(a[k],a[i]);
     quicksort(a, l, j);
     quicksort(a, i, r);
   }

Упражнения

7.34. Поясните, что произойдет, если программа 7.5 будет запущена для случайно упорядоченного файла (1) с двумя различными значениями ключей и (2) с тремя различными значениями ключей.

7.35. Измените программу 7.1 так, чтобы выполнялась команда return, если все ключи в подфайле равны. Сравните эффективность полученной программы с программой 7.1 для больших случайно упорядоченных файлов с ключами, принимающими t различных значений для t = 2, 5 и 10.

7.36. Предположим, в программе 7.2 просмотр не останавливается на ключах, равных центральному, а пропускает их. Покажите, что в этом случае время выполнения программы 7.1 будет квадратичным.

7.37. Докажите, что время выполнения программы из упражнения 7.36 квадратично для всех файлов с 0(1) различными значениями ключей.

7.38. Напишите программу для определения количества различных ключей, встречающихся в файле. Воспользуйтесь полученной программой для подсчета различных ключей в случайно упорядоченных файлах, содержащих N целых чисел из диапазона от 0 до M- 1 для M = 10, 100 и 1000 и для N = 10³, 10⁴, 10⁵ и 10⁶.

Строки и векторы

Когда ключами сортировки являются строки, можно воспользоваться реализацией типа данных наподобие программы 6.11 совместно с реализациями быстрой сортировки из данной главы. В результате получится корректная и эффективная реализация (для больших файлов быстрее любого другого рассмотренного нами метода), но в ней будут присутствовать неявные издержки, которые стоит рассмотреть подробнее.

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

Например, рассмотрим подфайл размером 5, содержащий ключи discreet, discredit, discrete, discrepancy и discretion. Все сравнения при сортировке этих ключей проверяют по меньшей мере семь символов, в то время как достаточно начать с седьмого символа - если бы дополнительно было известно, что первые шесть символов совпадают.

Процедура трехчастного разбиения, рассмотренная в разделе 7.6, обеспечивает элегантный способ использовать это соображение. На каждой стадии разбиения проверяется лишь один символ (скажем, символ в позиции d), считая, что сортируемые ключи совпадают в позициях с 0 по ). Это убедительный пример мощи рекурсивного мышления (и программирования).

В таблица 7.2 представлены относительные затраты для нескольких различных вариантов быстрой сортировки на примере упорядочения первых N слов из книги Г Мелвилла " Моби Дик " . Использование сортировки вставками непосредственно для небольших подфайлов или их игнорирование с последующей сортировкой вставками являются эквивалентными по эффективности стратегиями, но снижение затрат здесь несколько ниже, чем для целочисленных ключей (см. таблица 7.1), т.к. сравнение строк более трудоемко. Если во время разбиения файлов не останавливаться на повторяющихся ключах, тогда время сортировки файла со всеми одинаковыми ключами квадратично. Эта неэффективность видна в приведенном примере, т.к. в тексте есть много слов, встречающихся с большой частотой. По этой причине эффективно трехчастное разбиение, которое на 30-35% быстрее системной сортировки.

Эмпирическое сравнение вариантов быстрой сортировки строковых ключей
N	V	I	M	Q	X	T
12500	8	7	6	10	7	6
25000	16	14	13	20	17	12
50000	37	31	31	45	41	29
100000	91	78	76	103	113	68

Обозначения:
V	Быстрая сортировка (программа 7.1)
I	Сортировка вставками для подфайлов небольших размеров
M	Игнорирование небольших подфайлов с последующей сортировкой вставками
Q	Системная сортировка qsort
X	Пропуск повторяющихся ключей (квадратичное время для всех равных ключей)
T	Трехчастное разбиение (программа 7.5)

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

Этот подход можно распространить на многомерные сортировки, где ключами сортировки являются векторы, а записи должны быть отсортированы таким образом, что ключи упорядочены по первой компоненте, а записи с равными первыми компонентами ключей упорядочены по второй компоненте и т.д. Если компоненты не содержат повторяющихся ключей, задача сводится к сортировке по первой компоненте; однако в типичных приложениях каждая из компонент может принимать лишь нескольких различных значений, и поэтому применимо трехчастное разбиение (переходящее к следующей компоненте в среднем подфайле). Этот случай имеет важное практическое применение, рассмотренное Хоаром (Hoare) в его оригинальной работе.

Упражнения

7.39. Рассмотрите возможность усовершенствования сортировки выбором, сортировки вставками, пузырьковой сортировки и сортировки Шелла для упорядочения строк.

7.40. Сколько символов проверяет стандартный алгоритм быстрой сортировки (программа 7.1, использующая строковый тип из программы 6.11) при сортировке файла, состоящего из одинаковых N строк длиной t ? Ответьте на этот же вопрос для модификации, предложенной в тексте.

Выборка

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

Операция нахождения медианы представляет собой частный случай операции выборки (selection): нахождения к-го наименьшего числа из некоторого множества чисел. (Не спутайте эту выборку со случайной выборкой (sample), введенной в разделе 7.5 - прим. перев.) Поскольку алгоритм не может гарантировать, что конкретный элемент является к-ым наименьшим, без проверки к - 1 меньших элементов и N - к больших элементов, большинство алгоритмов выборки может возвратить все к наименьших элементов файла без существенных дополнительных вычислений.

Выборки часто применяются при обработке экспериментальных и других данных. Широко практикуется использование медианы и других характеристик положения (order statistics) для деления файла на меньшие группы. Нередко для дальнейшей обработки нужно сохранить лишь небольшую часть большого файла; в таких случаях программа, способная выбрать, скажем, 10% наибольших элементов файла, может оказаться предпочтительнее полной сортировки. Другим важным примером является использование разбиения по медиане в качестве первого шага во многих алгоритмах вида " разделяй и властвуй " .

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

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

(рис 7.13) Выборка медианы

Для ключей из данного примера выборка разбиением требует только три рекурсивных вызова на поиск медианы. В первом вызове ищется восьмой наименьший элемент в файле из 15 элементов, а разбиение дает четвертый наименьший (элемент E). Поэтому во втором вызове ищется четвертый наименьший элемент в файле из 11 элементов (элемент R). И поэтому в третьем вызове ищется четвертый наименьший элемент в файле из 7 элементов - и он находится (элемент M). Файл переупорядочивается таким образом, что медиана находится на своем месте, меньшие элементы - слева от нее, а большие - справа (равные элементы могут находиться с любой стороны), но полной упорядоченности нет.

Программа 7.6. Выборка

Данная процедура разбивает массив по (k-1-му наименьшему элементу (который находится в a[k]): она переупорядочивает массив так, что a[1], ..., a[k-1] меньше или равны a[k], а a[k+1], ..., a[r] больше или равны a[k].

Например, можно вызвать select(a,0,N-1,N/2) для разбиения массива по медиане так, чтобы медиана осталась в a[N/2].

template <class Item>
  void select(Item a[], int l, int r, int k)
    {
      if (r <= l) return;
      int i = partition(a, l, r);
      if (i > k) select(a, l, i-1, k);
      if (i < k) select(a, i+1, r, k);
    }

Программа 7.7 является нерекурсивной версией, непосредственно вытекающей из рекурсивной версии в программе 7.6. Поскольку программа 7.6 всегда завершается одиночным вызовом самой себя, мы просто переустанавливаем параметры и возвращаемся в начало. Таким образом мы избавились от рекурсии, не используя стек, а также избавились от вычислений, использующих k, храня его как индекс массива.

Лемма 7.4. Выборка, основанная на быстрой сортировке, в среднем выполняется за линейное время.

Как и в случае быстрой сортировки, можно (грубо) предположить, что для очень больших файлов каждое разбиение делит массив приблизительно пополам, так что весь процесс потребует примерно N + N/2 + N/4 + N/8 + ... = 2N операций сравнения. И так же, как и для быстрой сортировки, это грубое приближение недалеко от истины. Анализ, подобный приведенному в разделе 7.2 для быстрой сортировки, но гораздо более сложный (см. раздел ссылок), приводит к тому, что порядок среднего количества сравнений равен выражению

2 N + 2^kln (N/ k) + 2(N - k) ln (N / (N - k)),

которое линейно для любого допустимого значения к. При к = N/ 2 из этой формулы следует, что для нахождения медианы требуется порядка (2 + 2 ln 2) N сравнений. $$$\blacksquare$$$

Программа 7.7. Нерекурсивная выборка

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

template <class Item>
  void select(Item a[], int l, int r, int k)
    {
      while (r > l)
        { int i = partition(a, l, r);
if (i >= k) r = i-1;
if (i <= k) l = i+1;
        }
    }

Пример того, как этот метод находит медиану в большом файле, приведен на рис 7.14. Здесь имеется лишь один подфайл, размер которого при каждом вызове уменьшается в одно и то же число раз, так что эта процедура завершается за O(log N) шагов. Программу можно ускорить, введя в нее разбиение по случайной выборке, но при этом следует соблюдать осторожность (см. упражнение 7.45).

(рис 7.14) Выборка медианы с помощью разбиений

В процессе выборки выполняется разбиение подфайла, который содержит искомый элемент. В зависимости от того, куда попадает разбиение, левый индекс перемещается вправо или правый индекс перемещается влево.

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

Упражнения

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

7.42. Оцените среднее количество операций сравнения, требуемое для нахождения aN-го наименьшего элемента при использовании метода select, для a = 0.1, 0.2, ... , 0.9.

7.43. Сколько потребуется операций сравнения в худшем случае для нахождения медианы из N элементов при использовании метода select?

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

7.45. Обдумайте идею усовершенствования выборки с помощью оценки по случайной выборке. Совет: использование медианы помогает не всегда.

7.46. Реализуйте алгоритм выборки на базе трехчастного разбиения для больших случайно упорядоченных файлов с ключами, принимающими t различных значений, для t = 2, 5 и 10.

Страницы:

Базовый алгоритм

Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.

Ни один из элементов a[i], ..., a[i-1] не является большим a[i].

Ни один из элементов a[i+1], ..., a[r] не является меньшим a[i].

(рис 7.1) Пример работы быстрой сортировки

Программа 7.1. Быстрая сортировка

template <class Item>
  void quicksort(Item a[], int l, int r)
    {
      if (r <= l) return;
      int i = partition(a, l, r);
      quicksort(a, l, i-1);
      quicksort(a, i+1, r);
    }

(рис )

Здесь и рис 7.3.

(рис 7.2) Разбиение при работе быстрой сортировки

Программа 7.2. Разбиение

template <class Item>
  int partition(Item a[], int l, int r)
    { int i = l-1, j = r; Item v = a[r]; 
      for (;;)
        {
while (a[++i] < v) ;
while (v < a[-j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
        }
        exch(a[i], a[r]);
        return i;
    }

(рис 7.3) Динамические характеристики разбиения при работе быстрой сортировки

Упражнения

7.1. Покажите в стиле вышеприведенного примера, как быстрая сортировка сортирует файл E A S Y Q U E S T I O N.

7.3. Реализуйте разбиение без использования операторов break или goto.

7.4. Разработайте устойчивую быструю сортировку для связных списков.

Характеристики производительности быстрой СОРТИРОВКИ

Лемма 7.1. Быстрая сортировка в худшем случае выполняет порядка N²/2 сравнений.

N + (N - 1) + (N - 2) + ... + 2 + 1 = (N + 1) N/ 2.

C_N = 2C_N/2 + N

Во-вторых, можно избавиться от суммы, умножив обе части равенства на N и вычтя эту же формулу для N- 1:

NC_N - (N - 1)C_N-1 = N (N + 1) - (N - 1)N + 2C_N-1 .

Эта формула упрощается до рекуррентного соотношения

NC_N = (N + 1)C_N-1 + 2N.

В третьих, разделив обе части на N (N + 1), получим соотношение, которое далее сворачивается:

(рис 7.4) Динамические характеристики быстрой сортировки при обработке различных видов файлов

Упражнения

Размер стека

(рис 7.5) Размер стека при работе быстрой сортировки

Программа 7.3. Нерекурсивная быстрая сортировка

  #include "STACK.cxx"
  inline void push2(STACK<int> s, int A, int B)
    { s.push(B); s.push(A); }
template <class Item>
  void quicksort(Item a[], int l, int r)
    { STACK<int> s(50)); push2(s, l, r);
      while (!s.empty())
        {
l = s.pop(); r = s.pop();
if (r <= l) continue;
int i = partition(a, l, r);
if (i-1 > r-i)
  { push2(s, l, i-1); push2(s, i+1, r); }
else
  { push2(s, i+1, r); push2(s, l, i-1); }
        }
    }

(рис 7.6) Пример работы быстрой сортировки (вначале упорядочивается меньший подфайл)

(рис 7.7) Дерево разбиений быстрой сортировки

Упражнения

7.13. Завершите доказательство по индукции леммы 7.3.

7.14. Внесите в программу 7.3 такие изменения, чтобы она никогда не помещала в стек подфайлы с $$$r\leq l$$$ .

7.15. Приведите максимальный размер стека, требуемый программой 7.3 при N = 2ⁿ.

7.16. Приведите максимальные размеры стека, требуемые программой 7.3 при N = 2ⁿ - 1 и N = 2ⁿ + 1.

7.18. Определите, выполняется ли в вашей системе программирования освобождение стека перед выходом.

Подфайлы небольшого размера

  if (r-1 <= M) insertion(a, l, r);

(рис 7.8) Отсечение небольших подфайлов

  if ( r-1 <= M) return;

(рис 7.9) Сравнения в быстрой сортировке

Упражнения

7.21. Нужны ли сигнальные ключи, если сортировка вставками вызывается непосредственно из быстрой сортировки?

7.24. Выполните упражнение 7.23, используя нерекурсивную реализацию.

Разбиение по медиане из трех

(рис 7.10) Размер стека для усовершенствованного варианта быстрой сортировки

Программа 7.4. Усовершенствованная быстрая сортировка

  static const int M = 10;
  template <class Item>
  void quidcksort(Item a[], int l, int r)
    {
      if (r-1 <= M) return;
      exch(a[(l+r)/2], a[r-1]);
      comexch(a[l], a[r-1]);
      comexch(a[l], a[r]);
      comexch(a[r-1], a[r]);
      int i = partition(a, l+1, r-1);
      quicksort(a,l, i-1);
      quicksort(a, i+1, r);
    }
  template <class Item>
  void hybridsort(Item a[], int l, int r)
    { quicksort(a, l, r); insertion(a, l, r); }

Эмпирическое сравнение алгоритмов быстрой сортировки
N	Шелла	Базовая быстрая сортировка			Быстрая сортировка с разбиением по медиане из трех
N	Шелла	`M = 0`	`M = 10`	`M = 20`	`M = 0`	`M = 10`	`M = 20`
12500	6	2	2	2	3	2	3
25000	10	5	5	5	5	4	6
50000	26	11	10	10	12	9	14
100000	58	24	22	22	25	20	28
200000	126	53	48	50	52	44	54
400000	278	116	105	110	114	97	118
800000	616	255	231	241	252	213	258

Упражнения

7.31. Реализуйте быструю сортировку с использованием случайной выборки из 2^k - 1

7.32. Определите эмпирическим путем наилучший размер выборки для сортировки

Повторяющиеся ключи

(рис 7.12) Трехчастное разбиение

Программа 7.5. Быстрая сортировка с трехчастным разбиением

  template <class Item>
  int operator==(const Item A, const Item B)
    { return !less(A, B)  !less(B, A); }
  template <class Item>
  void quicksort(Item a[], int l, int r)
    { int k; Item v = a[r];
      if (r <= l) return;
      int i = l-1, j = r, p = l-1, q = r;
      for (;;)
        {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i],a[j]);
if (a[i] == v) { p++; exch(a[p],a[i]); }
if (v == a[j]) { q-; exch(a[q],a[j]); }
       }
     exch(a[i], a[r]); j = i-1; i = i+1;
     for (k = l ; k <= p; k++, j -) exch(a[k],a[j]);
     for (k = r-1; k >= q; k--, i++) exch(a[k],a[i]);
     quicksort(a, l, j);
     quicksort(a, i, r);
   }

Упражнения

Строки и векторы

Эмпирическое сравнение вариантов быстрой сортировки строковых ключей
N	V	I	M	Q	X	T
12500	8	7	6	10	7	6
25000	16	14	13	20	17	12
50000	37	31	31	45	41	29
100000	91	78	76	103	113	68

Обозначения:
V	Быстрая сортировка (программа 7.1)
I	Сортировка вставками для подфайлов небольших размеров
M	Игнорирование небольших подфайлов с последующей сортировкой вставками
Q	Системная сортировка qsort
X	Пропуск повторяющихся ключей (квадратичное время для всех равных ключей)
T	Трехчастное разбиение (программа 7.5)

Упражнения

Выборка

(рис 7.13) Выборка медианы

Программа 7.6. Выборка

Например, можно вызвать select(a,0,N-1,N/2) для разбиения массива по медиане так, чтобы медиана осталась в a[N/2].

template <class Item>
  void select(Item a[], int l, int r, int k)
    {
      if (r <= l) return;
      int i = partition(a, l, r);
      if (i > k) select(a, l, i-1, k);
      if (i < k) select(a, i+1, r, k);
    }

Лемма 7.4. Выборка, основанная на быстрой сортировке, в среднем выполняется за линейное время.

2 N + 2^kln (N/ k) + 2(N - k) ln (N / (N - k)),

Программа 7.7. Нерекурсивная выборка

template <class Item>
  void select(Item a[], int l, int r, int k)
    {
      while (r > l)
        { int i = partition(a, l, r);
if (i >= k) r = i-1;
if (i <= k) l = i+1;
        }
    }

(рис 7.14) Выборка медианы с помощью разбиений

Упражнения

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Базовый алгоритм

Характеристики производительности быстрой СОРТИРОВКИ

Размер стека

Подфайлы небольшого размера

Разбиение по медиане из трех

Повторяющиеся ключи

Строки и векторы

Выборка

Базовый алгоритм

Характеристики производительности быстрой СОРТИРОВКИ

Размер стека

Подфайлы небольшого размера

Разбиение по медиане из трех

Повторяющиеся ключи

Строки и векторы

Выборка

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!