Структуры данных и алгоритмы (1021739), страница 61
Текст из файла (страница 61)
При п > 1 требуетсявремя с2п (с2 — некоторая константа), чтобы определить опорное значение и разбитьисходное множество элементов на два подмножества; после этого вызывается процедура quicksort для каждого из этих подмножеств. Было бы хорошо (с точки зренияанализа алгоритма), если бы мы могли утверждать, что для подмножества, котороеупорядочивается данным вызовом процедуры quicksort, опорное значение с одинаковой вероятностью может быть равным любому из п элементов исходного множества.Но в этом случае мы не можем гарантировать, что такое опорное значение сможетразбить это подмножества на два других непустых подмножества, одно из которыхсодержало бы элементы, меньшие этого опорного значения, а другое — равные илибольшие его.
Другими словами, в рассматриваемом подмножестве с ненулевой вероятностью могут находиться только элементы, меньшие этого опорного значения, либо, наоборот, большие или равные опорному значению. Именно по этой причине валгоритме быстрой сортировки опорное значение выбирается как наибольшее значение ключей первых двух различных элементов.
Отметим, что такое определениеопорного значения не приводит к эффективному (т.е. примерно равному) размеруподмножеств, на которые разобьется рассматриваемое подмножество относительноэтого опорного значения. При таком выборе опорного значения можно заметить тенденцию, что "левое" подмножество, состоящее из элементов, чьи ключи меньшеопорного значения, будет больше "правого" подмножества, состоящего из элементов,ключи которых больше или равны опорному значению.Предполагая, что все сортируемые элементы различны, найдем вероятность того,что "левое" подмножество будет содержать i из п элементов.
Для того чтобы "левое"подмножество содержало i элементов, необходимо, чтобы опорное значение совпадалос (i 4- 1)-м порядковым значением в последовательности упорядоченных в возрастающем порядке элементов исходного множества. При нашем методе выбора опорного значения данное значение можно получить в двух случаях: (1) если элемент созначением ключа, равного (i + 1)-му порядковому значению, стоит в первой позиции,во второй позиции стоит любой из i элементов с ключами, меньшими, чем у первогоэлемента; (2) элемент со значением ключа, равного новому опорному значению, стоитна второй позиции, а в первой — любой из i элементов с ключами, меньшими чем увторого элемента.
Вероятность того, что отдельный элемент, такой как (i + l)-e порядковое значение, появится в первой позиции, равна 1/л. Вероятность того, чтово второй позиции будет стоять любой из i элементов со значением ключа, меньшим, чем у первого элемента, равна i/(n - 1). Поэтому вероятность того, что новоеопорное значение находится в первой позиции, равна i/n(n - 1). Такое же значениеимеет вероятность события, что новое опорное значение появится во второй позиции. Отсюда вытекает, что "левое" множество будет иметь размер i с вероятность2i/n(n - 1) для 1 < i < п.Теперь можно записать рекуррентное соотношение для Т(п):2lТ(п) < §[Г(0 + Т(п - 1)] + с2п.ПТ п(п - 1)(8.1)Неравенство (8.1) показывает, что среднее время выполнения алгоритма быстрой сортировки не превышает времени с 2 л, прошедшего от начала алгоритма дорекурсивных вызовов quicksort, плюс среднее время этих рекурсивных вызовов.Последнее время является суммой по всем возможным i произведений вероятностей того, что "левое" множество состоит из i элементов (или, что то же самое, вероятностей того, что "правое" множество состоит из п - i элементов) и времени рекурсивных вызовов T(i) и Т(п - i).Теперь надо упростить сумму в выражении (8.1).
Сначала заметим, что для любойфункции /(i) путем замены i на п - i можно доказать следующее равенство:»-*>•1=1(8.2)i=lИз равенства (8.2) следует, что8.3. БЫСТРАЯ СОРТИРОВКА241(8 3)/("-*)).-Положив f(i) равными слагаемым в выражении (8.1) и применяя равенство (8.3), изнеравенства (8.1) получим) + Т(п - i)] + сгп.(8.4)Далее снова применяем формулу (8.3) к последней сумме в (8.4), положивЛО(8.5)-1(Отметим, что последнее неравенство в (8.4) соответствует выражению, котороемы получили бы, если бы предполагали равные вероятности для всех размеров (от1 до п) "левых" множеств.) Решение рекуррентных соотношений мы подробно рассмотрим в главе 9. Здесь мы покажем, как можно оценить сверху решение рекуррентного неравенства (8.5).
Мы докажем, что для всех п 2 2 Т(п) < en logn для некоторой константы с.Доказательство проведем методом индукции по п. Для п = 2 непосредственно изнеравенства (8.5) для некоторой константы с получаем Т(2) ^ 2с — 2с Iog2. Далее, всоответствии с методом математической индукции, предположим, что для i < п выполняются неравенства T(i) < cl logt.
Подставив эти неравенства в формулу (8.5), дляТ(п) получим(8.6)T(n)<-^-^ilogi + c2n.Л-1(=1Разобьем сумму в (8.6) на две суммы: в первой i <, п/2, во второй i > п/2. В первой сумме log i < log(ra/2) = log n - 1, во второй сумме log i не превышают log п. Таким образом, из (8.6) получаем2с- i g n l=n/2-t-l2cn-1+С 2 Л =42cn-l<cnlognn22»\(nnlogn- — + —2248 4+ c,n.2(n -1)(8.7)Если положить с > 4c2, тогда в последнем выражении сумма второго и четвертогослагаемых не превысит нуля. Третье слагаемое в последней сумме (8.7) отрицательное, поэтому можно утверждать, что Т(п) <, en logn для константы с = 4с2. Этим заканчивается доказательство того, среднее время выполнения алгоритма быстрой сортировки составляет О(п logn).242ГЛАВА 8.
СОРТИРОВКАРеализация алгоритма быстрой сортировкиАлгоритм быстрой сортировки можно реализовать не только посредством процедура quicksort так, чтобы среднее время выполнения равнялось О(п logn). Можносоздать другие процедуры, реализующие этот алгоритм, которые будут иметь тот жепорядок О(п logn) времени выполнения в среднем, но за счет меньшей константыпропорциональности в этой оценке будут работать несколько быстрее (напомним, чтопорядок времени выполнения, такой как О(п logn), определяется с точностью доконстанты пропорциональности).
Эту константу можно уменьшить, если выбиратьопорное значение таким, чтобы оно разбивало рассматриваемое в данный моментподмножество элементов на две примерно равные части. Если всегда такие подмножества разбиваются точно пополам, тогда каждый сортируемый элемент имеет глубину точно logn в дереве, аналогичном изображению из рис. 8.1 (вспомните полныедвоичные деревья из главы 5).
Для сравнения: средняя глубина элементов в процедуре quicksort (листинг 8.8) составляет 1.4 logn. Так что можно надеяться, что при"правильном" выборе опорного значения выполнение алгоритма ускорится.Например, можно с помощью датчика случайных чисел выбрать три элемента изподмножества и средний (по величине) из них назначить опорным значением. Можнотакже, задав некоторое число k, выбрать случайным образом (например, опять с помощью датчика случайных чисел) k элементов из подмножества, упорядочить ихпроцедурой quicksort или посредством какой-либо простой сортировки из раздела 8.2и в качестве опорного значения взять медиану (т.е. (k + 1)/2-й элемент) этих k элементов.1 Заметим в скобках, что интересной задачей является определение наилучшего значения k как функции от количества элементов в подмножестве, подлежащемсортировке. Если k очень мало, то среднее время будет близко к тому, как если бывыбирался только один элемент.
Если же k очень велико, то уже необходимо учитывать время нахождения медианы среди k элементов.Другие реализации алгоритма быстрой сортировки можно получить в зависимостиот того, что мы делаем в случае, когда получаются малые подмножества. Напомним,что в разделе 8.2 говорилось о том, что при малых п алгоритмы с временем выполнения О(п2) работают быстрее, чем алгоритмы с временем выполнения порядкаО(п logn). Однако понятие "малости" п зависит от многих факторов, таких как организация рекурсивных вызовов, машинная архитектура и компилятор языка программирования, на котором написана процедура сортировки. В книге [65] предлагается значение 9 в качестве порогового значения размера подмножества, ниже которого целесообразно применять простые методы сортировки.Существует еще один метод "ускорения" быстрой сортировки за счет увеличенияиспользуемого пространства памяти компьютера.
Отметим, что этот метод применим клюбым алгоритмам сортировки. Если есть достаточный объем свободной памяти, томожно создать массив указателей на записи массива А. Затем следует организоватьпроцедуру сравнения ключей записей посредством этих указателей. В этом случае нетнеобходимости в физическом перемещении записей, достаточно перемещать указатели,что значительно быстрее перемещения непосредственно записей, особенно когда онибольшие (состоят из многих полей). В конце выполнения процедуры сортировки указатели будут отсортированы слева направо, указывая на записи в нужном порядке. Затемсравнительно просто можно переставить сами записи в правильном порядке.Таким образом, можно сделать только п перестановок записей вместо О(п logn) перестановок, и эта разница особенно значительна для больших записей. Отрицательными аспектами такого подхода являются использование дополнительного объема памятидля массива указателей и более медленное выполнение операции сравнения ключей,поскольку здесь сначала, следуя за указателями, надо найти нужные записи, затем необходимо войти в записи и только потом взять значения поля ключа.1Поскольку в данном случае необходимо только значение медианы, то вместо упорядочивания всего списка из k элементов рациональнее применить один из быстрых алгоритмов нахождения значения медианы, описанных в разделе 8.7.8.3.
БЫСТРАЯ СОРТИРОВКА2438.4. Пирамидальная сортировкаВ этом разделе мы рассмотрим алгоритм сортировки, называемой пирамидаль1ной , его время выполнения в худшем случае такое, как и в среднем, и имеет порядок О(п logn). Этот алгоритм можно записать в абстрактной (обобщенной) форме,используя операторы множеств INSERT, DELETE, EMPTY и MIN, введенные в главах 4 и 5.
Обозначим через L список элементов, подлежащих сортировке, a S —множество элементов типа recordtype (тип записи), которое будет использоватьсядля хранения сортируемых элементов. Оператор MIN применяется к ключевомуполю записей, т.е. MIN(S) возвращает запись из множества S с минимальным значением ключа. В листинге 8.9 показан абстрактный алгоритм сортировки, которыймы далее преобразуем в алгоритм пирамидальной сортировки.Листинг 8.9. Абстрактный алгоритм сортировки(1)for x e L do(2)(3)INSERT (X, S) ;while not EMPTY(S) do begin(4)y:= MIN(S) ;(5)write-in(y) ;(6)DELETE (y, S)endВ главах 4 и 5 мы показали различные структуры данных, такие как 2-3 деревья,помогающие реализовать эти операторы множеств с временем выполнения O(logn).Если список L содержит п элементов, то наш абстрактный алгоритм требует выполнения п операторов INSERT, п операторов MIN, п операторов DELETE и п + 1 операторов EMPTY.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
