Улучшенные методы сортировки массивов: метод быстрой сортировки.

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

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

· пусть каким-то образом в исходном наборе выделен некий элемент 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 25 47 31 39 15 20

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

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

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

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

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

7. перестановка элементов 28 и 15: 13 20 15 17 09 25 47 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, которое также было и серединным элементом (пример был подобран специально). К сожалению, поиск медианы в массиве является задачей, сопоставимой по трудоемкости с самой сортировкой, поэтому были предложены другие, более простые правила выбора опорного элемента.

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

Вывод

В главе I были рассмотрены теоретические аспекты методов сортировки данных, была приведена их классификация, а также приведены критерии для оценки алгоритмов. На основе вышеизложенного были сделаны следующие выводы:

- Метод обмена (пузырька) имеет единственное преимущество – нулевое число пересылок в случае, если исходный набор уже отсортирован в нужном порядке. В остальных случаях все его показатели пропорциональны n².

- Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n). Во всех остальных случаях его показатели пропорциональны n², хотя что касается оценки среднего числа сравнений, то она чуть лучше, чем у других методов. Многочисленные эксперименты показывают, что метод вставок дает наименьшее время сортировки среди всех простейших методов.

- Метод выбора, как это и следовало ожидать, имеет лучшие показатели по числу пересылок, особенно – для общего случая, где оценка О(n*log ₂ n) заметно лучше оценки O(n²). Поэтому его можно рекомендовать к использованию из всех простейших методов в том случае, если именно число перестановок является наиболее важным.

- Метод Шелла – усовершенствованный метод вставок. Суть его заключается в многократном использовании метода вставок для небольшого набора данных. Трудоемкость данного метода выражается соотношением O(n^{1, 2}), что является его преимуществом.

- Метод быстрой сортировки является наиболее универсальным по отношению к вышеперечисленным методам. Недостатком метода является следующее: при малых n (десятки и сотни элементов) он неэффективен, но при значительном увеличении n его эффективность резко возрастает.