Фундаментальные алгоритмы и структуры данных в Delphi

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

Именно она является рекурсивной, и именно она - суть всей реализации. Первое, что необходимо отметить, - процедура QSS работает только в том случае, когда в сортируемом списке есть хотя бы два элемента. В качестве базового элемента выбирается средний элемент списка. Затем устанавливаются начальные значения для индексов L и R - перед первым элементом и после последнего элемента списка соответственно. После этого в процедуре организован бесконечный цикл - при необходимости мы сами выйдем из него с помощью оператора break. Обратите внимание, что внутренние циклы организованы с помощью операторов Repeat..until. В первом цикле уменьшается значение индекса R до тех пор, пока он не будет указывать на элемент, значение которого меньше или равно значению базового элемента. Во втором цикле значение индекса L увеличивается до тех пор, пока он не будет указывать на элемент, значение которого больше или равно значению базового элемента. Затем сравниваются значения индексов L и R. Если значение L больше или равно значению R, индексы встретились или пересеклись, и мы выходим из бесконечного цикла. В противном случае два элемента, на которые указывают индексы, меняются местами, и выполнение цикла продолжается.

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

QSS(aList, aFirst, R, aCompare);

QSS(aList, R+ 1, aList, aCompare);

Другими словами, рекурсивно выполняется сортировка первой части, а затем -второй части раздела. Один из самых простых хитростей искусства программирования заключается в исключении рекурсивного вызова в конце рекурсивной процедуры. Как правило, бывает достаточно изменения переменных в процедуре и перехода к ее началу. В QSS для исключения рекурсии используется цикл while при изменении значения переменной aFirst. Очень простой метод устранения рекурсии, не правда ли?

После изучения такого рода процедур, особенно процедур с циклами, любой программист начнет искать способы увеличения ее эффективности. В случае с быстрой сортировкой лучше не пытайтесь изменять приведенную процедуру. Даже незначительное изменение может привести к существенному снижению скорости работы или к тому, что бесконечный цикл оправдает свое название. Давайте рассмотрим несколько часто встречаемых ошибок. Первое желание - установить начальные значения индексов L и R так, чтобы они указывали на фактические первый и последний элементы списка, а не на предшествующий первому и следующий после последнего элементы, а затем заменить цикл Repeat..until циклом while, естественно, изменив условие цикла. По крайней мере, в этом случае можно исключить одну операцию декремента и одну - инкремента. Первый цикл превратиться в цикл "выполнять, пока больше чем", а второй - в цикл "выполнять, пока меньше чем". Если на вход такой "улучшенной" процедуры быстрой сортировки подавать список с произвольных расположением элементов, он будет работать без ошибок. Но для списка, все элементы которого равны, бесконечный цикл будет действительно выполняться бесконечно, поскольку значения индексов меняться не будут. Изменение условий циклов включает равенство, позволяет избежать зацикливания процедуры, но приводит к еще одной проблеме: индексы будут выходить за границы списка.

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

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

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