Главная » Java, Структуры данных и алгоритмы » Сравнение алгоритмов сортировки

0

Еще раз вернемся к пройденному материалу и проведем небольшой сравнительный анализ рассмотренных алгоритмов сортировки. Были представлены методы «bubble-sort», «insertion-sort» и «selection-sort», которые во всех случаях и при любых условиях выполняются за 0(п2) времени. Обсуждались также методы «heap-sort», «merge-sort» и «quick-sort» со временем выполнения 0(п log п). И наконец, показан специальный класс алгоритмов сортировки, а именно методы сегментной сортировки «bucket-sort» и поразрядной сортировки «radix-sort», выполняющиеся за линейное время для определенных типов ключей. Конечно, алгоритмы пузырьковой сортировки и выборочной сортировки не являются лучшим решением для приложений, поскольку даже в лучшем случае выполняются за 0(я2) времени. Но какой из алгоритмов лучше?

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

•      При верной реализации время выполнения сортировки методом ввода составляет Щп •+•Зк), где к — количество инверсий (то есть количество пар неупорядоченных элементов). Таким образом, сортировка методом ввода — прекрасный метод сортировки небольших последовательностей (скажем, не’более 50 элементов), поскольку эта сортировка легко программируется,’ а небольшие последовательности имеют небольшое количество инверсий. К тому же метод очень эффективен при сортировке «по^’ти упорядоченных» последовательностей. Под «почти упорядоченными» понимается минимальное количество Инверсий. Но время 0(п2) делает этот алгоритм Практически неприменимым вне рамок приведенного контекста.

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

•      Экспериментальные исследования также показали, что для последовательности, целиком размещаемой в основной памяти, внутренняя быстрая сортйровка и внутренняя пирамидальная сортировка выполняются быстрее сортировки методом слияния. В частности, быстрая сортировка в некоторых ситуациях даже опережает пирамидальную сортировку. Значит, быстрая сортировка — наилучший выбор для работы в пределах основной памяти. Не зря же этот метод включен в состав сортирующей утилиты qsort в библиотеках языка С. Но и тогда время выполнения 0(п2) делает это алгоритм бесполезным для приложений, которые должны работать в реальном времени, где должны быть гарантия определенного времени выполнения сортировочных операций.

•      В сценариях реального времени, когда для выполнения сортировочной операции отводится фиксированное время, а исходные данные целиком помещаются в основной памяти, наилучшим выбором наверняка будет алгоритм пирамидальной сортировки. Он требует 0(h log п) времени и может легко выполняться внутри постоянного объема памяти-.

•   И наконец, если приложение включает сортировку по целочислен-

. ным ключам или комбинациям целых чирел, то сегментная или поразрядная сортировки более применимы, так как затраты времени в этих случаях составляют 0(d(n_ + N)), где целочисленные ключи входят в диапазон [О, N— 1], a d = 1 (для сегментной сортировки). Таким образом, если d(n + N) меньше nlogn (формально d(n + N) равно о(п log п), см. п. 3.6.2), то этот метод сортировки работает быстрее, чем даже быстрая или пирамидальная сортировки.

Таким образом, имеется набор разнообразных алгоритмов сортировки, обеспечивающих различные сортировочные методы.

Выборка

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

В этом разделе обсуждается общая порядково-статистическая проблема выбора наименьшего элемента из несортированного множества п элементов, к которым применима операция сравнения, известная как задача выбора (selection problem). Естественно, решить такую задачу можно с помощью сортировки множества и присвоения индекса рангу к. При использовании наилучшего сравнительного сортировочного алгоритма потребуется 0(п log п) времени, что является неприемлемым для случаев, когда к = 1 или к = п (или даже к = 3, к = Я – 1, к — п – 5), поскольку для этих к вполне можно добиться времени О(п). Уместен вопрос о возможности затратить время О(п) для всех значений к (включая упомянутый случай с поиском медианы, когда к = [_п / 2J).

v

 «Отсекай и ищи»

Как бы это ни было удивительно, но действительно можно решить задачу выбора за О(п) времени для любого значения к. Более того, механизм, используемый для получения этого результата, содержит интересную алгоритмическую проектную модель, известную как «отсечение и поиск» («Отсекай и ищи»), или «уменьшение и слияние» («Сокращай и властвуй»), . При применении этой модели проблема, возникшая в множестве из п объектов, решается путем отсечения подмножеств объектов и рекурсивного решения меньших задач. Когда в конце концов задача сводится до подмножества объектов постоянного размера, ее разрешают «силовым методом». Возвращение всех рекурсивных вызовов завершает конструкцию. В некоторых случаях можно обойтись без рекурсии, пошагово выполняя итерации отсечения до тёх пор, пока не появится возможность решения напрямую. Совершенно случайно описанный в п. 8.5.1 поисковый метод может служить примером проектной модели «отсечение и поиск».

Рандомизированая быстрая выборка

Применяя «отсекающую» модель для решения задачи выбора, создадим простой и практичный метод под названием рандомизированная быстрая выборка (randomized quick select), который может использоваться

для поиска наименьшего элемента в неупорядоченной последовательности из п элементов, находящихся в отношениях полной упорядоченности. Рандомизированная быстрая выборка выполняется за предполагаемое время О(п), одинаковое для всевозможных вариантов выбора, определяемых алгоритмом, и не зависящее от вероятности расположения элементов исходного множества. Заметим, однако, что в самом неблагоприятном случае рандомизированная быстрая выборка выполняется за 0(п2) времени, доказательство чего оставляем для упражнения М-10.7. Упражнением 3-10.23 предполагается модифицировать рандомизированную быструю выборку для получения детерминированного алгоритма выбора, выполняющегося в худшем случае за О(п) времени. Наличие такого алгоритма представляет по большей части чисто теоретический интерес, так как постоянный коэффициент 0-нотации в этом случае относительно велик.

Предположим, имеется несортированная последовательность S из п сравнимых элементов, а также целочисленное к е [1, п]. Не вдаваясь в подробйости реализации, можно сказать, что алгоритм быстрой выборки для поиска наименьшего элемента в S структурно подобен алгоритму рандомизированной быстрой сортировки, описанному в п. 10.3.2. В Sвыбирается произвольный элемент х в качестве точки отсчета для деления S на подпоследовательности L, Е и G, соответственно сохраняющие элементы из S, меньшие х, равные х и большие х. Это стадия отсечения. Затем, пользуясь значением к, определяем подлежащий рекурсии набор. Рандомизированная быстрая выборка описана во фрагменте кода 10.9.

Алгоритм quickSelect(5,A;):

Input: последовательность S из п элементов и целочисленный к е [1, п].

Output: наименьший элемент последовательности S с ключом к.

if п = 1 then

return (первый) элемент из S. выбрать случайный элемент х из S

удалить все элементы S и разместить их в трех последовательностях:

•   L, элементы меньше х

•  Е, элементы равные х

•   G, элементы больше х.

if к < \L\ then

quickSelect(L,/c) else if к < \LMB then

return x {каждый элемент E равен x} else

quickSelect(G, k-ILI-IEf) {новый параметр выбора} Фрагмент кода 10.9. Алгоритм^ рандомизированной быетрйй выборки

.7.3. Анализ рандомизированной быстрой выборки*

Как уже упоминалось, алгоритм рандомизированной быстрой выборки выполняется за предполагаемое О(п) время. К счастью, обосновать это утверждение можно с помощью простейших свойств теории вероятности. Основным вероятностным свойством при этом является линейность математического ожидания (linearity of expectation). Согласно этому для произвольных переменных X, Yи числа с выполняются соотношения:

Е(Х + Y) =Е(Х) +E{Y) Е(сХ) = сЕ(Х),

а ожидаемое значение выражения Z обозначается E(Z).

Пусть t(n) — предполагаемое время выполнения рандомизированной быстрой выборки в последовательности размером п. Так как алгоритм такой сортировки зависит от случайных событий, время его выполнения t(n) также является случайной переменной. Для решения задачи следует определить границы E(t(n)), то есть границы изменения t(n). Допустим, рекурсивный вызов рандомизированной быстрой выборки будет «удачным», если он делит Этаким образом, что размер Ln G максимально равен Зп/4. Точнее, рекурсивный вызов будет удачным с вероятностью 1/2. Пусть g(n) обозначает количество последовательно выполняемых рекурсивных вызовов (включая текущий) до получения удачного вызова. Тогда

t(n) < bn ? g(n) + t(3n / 4),

где b > 1 является константой (соответствующей дополнительным затратам каждого вызова). Остановимся на случае п > 1, а для п = 1 доопределим функцию, задав значение Г(1) = Ь. Применяя свойство линейности математического ожидания в общем случае, получим

E(t(n)) < E(bn • g(n) + t(3n / 4)) = bn • E(g(n)) + E(t(3n / 4)).

Поскольку вероятность удачного рекурсивного вызова составляет 1/2 и не зависит от того, удачным или неудачным был вызов в его родительском элементе, предполагаемое значение g(n) равно предполагаемому количеству подкидываний монеты до выпадения «орла». Это предполагает, что E(g(n)) = 2. Отсюда, определив E(t(n)) через Т(п) (предполагаемое время выполнения алгоритма рандомизированной быстрой выборки), и для п > 1 можно записать следующее:

Т(п) < Т(3п / 4) + 2bn.

Как и в случае сортировки слиянием, повторно применим данное уравнение, поскольку п велико. Так, после двух итераций получим

Отсюда в общем случае

Таким образом, согласно утверждению 3.3 о геометрической прогрессии, в результате получим, что Т{п) есть О(п). В итоге сформулируем следующее.

Утверждение 10.8. Ожидаемое время выполнения рандомизированной быстрой сортировки в последовательности размером п составляет О(п).

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии