Метод быстрой сортировки

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

Более конкретно, алгоритм быстрой сортировки заключается в следующем.

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

· просматривается часть массива, расположенная левее опорного элемента и находится первый по порядку элемент a_i > x

· после этого просматривается часть массива, расположенная правее опорного элемента, причем - в обратном порядке, и находится первый по порядку (с конца) элемент a_j < x

· производится перестановка элементов a_i и a_j

· после этого в левой части, начиная с a_i отыскивается еще один элемент, больший x, а в правой части, начиная с a_j отыскивается элемент, меньший х

· эти два элемента меняются местами

· эти действия (поиск слева и справа с последующим обменом) продолжаются до тех пор, пока не будет достигнут опорный элемент x

· после этого слева от опорного элемента x будут находиться элементы, меньшие опорного, а справа – элементы, большие опорного. При этом обе половины скорее всего не будут отсортированными

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

Пример. Пусть исходный набор включает 11 чисел: 13-42-28-17-09-25-47-31-39-15-20. Основные шаги сортировки:

1. Выбор серединного элемента 25 (индекс 6): 13 42 28 17 09 2547 31 39 15 20

2. поиск слева первого элемента, большего 25: 42 (2 сравнения)

3. поиск справа от конца первого элемента, меньшего 25: 20 (1 сравнение)

4. перестановка элементов 42 и 20: 13 20 28 17 09 2547 31 39 15 42

5. поиск слева от 25 еще одного элемента, большего 25: 28 (1 сравнение)

6. поиск справа от 25 еще одного элемента, меньшего 25: 15 (1 сравнение)

7. перестановка элементов 28 и 15: 13 20 15 17 09 2547 31 39 28 42

8. поиск слева от 25 еще одного элемента, большего 25: нет (2 сравнения)

9. поиск справа от 25 еще одного элемента, меньшего 25: нет (3 сравнения)

10. теперь слева от 25 все элементы меньше 25, а справа – больше

11. выделяем отдельно левую часть: 13 20 15 17 09

12. выбираем серединный элемент 15 (индекс 3): 13 20 15 17 09

13. поиск слева от 15 элемента, большего 15: 20 (2 сравнения)

14. поиск справа от 15 элемента, меньшего 15: 09 (1 сравнение)

15. перестановка 20 и 09: 13 09 15 17 20

16. поиск справа от 15 еще одного элемента, меньшего 15: нет (1 сравнение)

17. теперь слева от 15 все элементы меньше 15, а справа – больше

18. поскольку слева от 15 только 2 элемента, просто сравниваем их друг с другом и переставляем (09 и 13)

19. поскольку справа от 15 только 2 элемента, просто сравниваем их и не переставляем

20. получаем для левой части упорядоченный набор: 09 13 15 17 20

21. возвращаемся к правой части: 47 31 39 28 42

22. выделяем серединный элемент 39 (индекс в данном поднаборе – 3): 47 31 39 28 42

23. поиск слева от 39 элемента, большего 39: 47 (1 сравнение)

24. поиск справа от 39 элемента, меньшего 39: 28 (2 сравнения)

25. переставляем 47 и 28: 28 31 39 47 42

26. поиск слева от 39 еще одного элемента, большего 39: нет (1 сравнение)

27. теперь слева от 39 все элементы меньше 39, а справа – больше

28. поскольку слева от 39 только 2 элемента, просто сравниваем их и не переставляем

29. поскольку справа от 39 только 2 элемента, просто сравниваем их и переставляем (42 и 47)

30. получаем для правой части упорядоченный набор: 28 31 39 42 47

31. вместе с левой частью и серединным элементом 25 получаем окончательный результат

Итого для данного примера потребовалось 22 сравнения и 6 пересылок.

В целом, оценка трудоемкости метода быстрой сортировки является типичной для улучшенных методов и выражается соотношением (n*log ₂ n)/6. Отсюда следует, что данный метод неэффективен при малых n (десятки или сотни элементов), но с ростом n его эффективность резко растет, и при очень больших n метод дает наилучшие показатели среди всех универсальных методов сортировки.

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

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

На практике хорошо показал себя следующий способ: выбрать случайно в массиве три элемента и взять в качестве опорного средний из них. Этот способ очень прост в реализации, т.к. требует только двух сравнений, но, конечно, он может обеспечивать хорошие показатели только в среднем, и не гарантирует идеальное поведение алгоритма абсолютно для ЛЮБЫХ входных данных.

Есть и другие усовершенствования базового алгоритма быстрой сортировки. Среди них:

· Проверка каждого подмассива на возможную упорядоченность перед самой сортировкой

· Для малых подмассивов (n < 10) разумно проводить сортировку с помощью более простых методов, например – Шелла

Комбинация всех этих методов известна как метод Синглтона [7].

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

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

Procedure QuickSort (left, right : integer);

{формальные параметры для запоминания границ}

var i, j : integer;

sred, temp : <описание элемента исходного массива>;

Begin

i := left; j := right; {установка начальных значений границ подмассива}

sred := mas [(left + right) div 2]; {определение серединного элемента}

Repeat

while (mas [i] < sred) do i := i + 1;

{поиск слева элемента, большего опорного}

while (mas [j] > sred) do j := j – 1;

{поиск справа элемента, меньшего опорного}

if i <= j then

begin{обмениваем элементы и изменяем индексы}

temp := mas [i]; mas [i] := mas [j]; mas [j] := temp;

i := i + 1; j := j –1;

end;

until i > j;

if left < j then QuickSort (left , j); {обработка левой половины}

if i < right then QuickSort (i , right); {обработка правой половины}

end;

Первоначальный вызов этой процедуры производится в главной программе в виде QuickSort (1, n); здесь n – число элементов в массиве.