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

0

Следующим сортировочным алгоритмом, приводимым ниже, будет быстрая сортировка (quick-sort). Этот алгоритм также основан на принципе «разделяй и властвуй», но применяет его методику в обратном порядке, так как вся основная работа выполняется в начале, до рекурсивного вызова.                                                                                                                    ‘

Высокоуровневое описание быстрой сортировки

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

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

Рис. 10.8. Схематическое представление алгоритма быстрой сортировки

1.     Разделение. Если S содержит хотя бы два элемента (при одном или отсутствии элементов сортировка не требуется), выбирается специальный элемент х, который будет называться точкой отсчета (pivot). Обычно таким элементЬм выбирается последний элемент S. Удалим все элементы из S и разложим их в три последовательности:

•     L — для хранения элементов S, меньших х\

•     Е — для хранения элементов S, равных х;

•      G — для хранения элементов S, больших х.

Естественно, поскольку элементы в S являются уникальными, то Е будет содержать только один элемент — саму точку отсчета.

2.     Рекурсия. Рекуррентная сортировка последовательностей L и G.

3.      Слияние. Складываем элементы обратно в S — сначала из L, затем из Е и, наконец, из G.

Аналогично алгоритму сортировки методом слияния, быстрая сортировка может быть представлена с помощью бинарного рекуррентного дерева, называемого деревом быстрой сортировки (quick-sort tree). На рис. 10^.9 приводится отображение алгоритма быстрой сортировки, где показана обработка исходной и полученной в результате последовательностей в каждом узле дерева быстрой сортировки. Пошаговое изменение дерева показано на рис. 10.10, 10.11 и 10.12.

(а)

Рис. 10.9. Дерево быстрой сортировки Тдля выполнения алгоритма быстрой сортировки в последовательности из 8 элементов: (а) исходные последовательности, обрабатывающиеся в каждом узле Т\ (Ь) полученные в результате последовательности, сгенерированные в каждом узле Т. На каждом уровне рекурсии выбирается своя точка отсчета, выделенная жирным шрифтом

(b) ‘

Но, в отличие от сортировки слиянием, высота дерева быстрой сортировки в худшем случае будет линейной. Это связано с тем, что последовательность, состоящая из п уникальных элементов, уже упорядочена. В таком случае обычный подход к выбору точки отсчета в виде последнего элемента последовательности, то есть наибольшего, приводит к тому, что L будет иметь размер п – 1, размер Е будет равен 1, а Сбудет вообще пустой. При каждом вызове сортировки в подпоследовательности L размер ее будет уменьшаться на 1. Следовательно, высота дерева быстрой сортировки составит п – 1.

Рис. 10.10. Изображение быстрой сортировки. Каждый узел дерева представляет рекурсивный вызов. Узлы, выделенные пунктиром, показывают еще не осуществленные вызовы. Узлы, выделенные жирной линией, отображают выполняющиеся вызовы. Узлы, выделенные тонкой линией, — выполнившиеся вызовы. На остальных узлах — зависшие вызовы (то есть активные вызовы, ожидающие выполнения вызовов в своих дочерних элементах). Обратите внимание на стадии деления, показанные в (b), (d) и (j) (продолжение на рис. 10.11)

Рис. 10.11 (продолжение рис. 10.10). Изображение быстрой сортировки. Обратите внимание на стадию слияния в (к)

Рис. 10.12 (продолжение рис. 10.11). Изображение быстрой сортировки. Несколько вызовов между (р) и (q) пропущены. Обратите внимание на стадии слияния в (о) и (г)

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

По теме:

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