Алгоритм. Быстрая сортировка использует стратегию «разделяй и властвуй»

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:

· Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

· Вычисляется индекс опорного элемента m.

· Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.

· Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

· Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

· Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

Пример:

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

1. Выбор серединного элемента 25 (индекс 6): 13 42 28 17 9 25 47 31 39 15 20
2. поиск слева первого элемента, большего 25: 42 (2 сравнения)
3. поиск справа от конца первого элемента, меньшего 25: 20 (1 сравнение)
4. перестановка элементов 42 и 20: 13 20 28 17 9 25 47 31 39 15 42
5. поиск слева от 25 еще одного элемента, большего 25: 28 (1 сравнение)
6. поиск справа от 25 еще одного элемента, меньшего 25: 15 (1 сравнение)
7. перестановка элементов 28 и 15: 13 20 15 17 9 25 47 31 39 28 42
8. поиск слева от 25 еще одного элемента, большего 25: нет (2 сравнения)
9. поиск справа от 25 еще одного элемента, меньшего 25: нет (3 сравнения)
10. теперь слева от 25 все элементы меньше 25, а справа – больше
11. выделяем отдельно левую часть: 13 20 15 17 9
12. выбираем серединный элемент 15 (индекс 3): 13 20 15 17 9
13. поиск слева от 15 элемента, большего 15: 20 (2 сравнения)
14. поиск справа от 15 элемента, меньшего 15: 9 (1 сравнение)
15. перестановка 20 и 9: 13 9 15 17 20
16. поиск справа от 15 еще одного элемента, меньшего 15: нет (1 сравнение)
17. теперь слева от 15 все элементы меньше 15, а справа – больше
18. поскольку слева от 15 только 2 элемента, просто сравниваем их друг с другом и переставляем (9 и 13)
19. поскольку справа от 15 только 2 элемента, просто сравниваем их и не переставляем
20. получаем для левой части упорядоченный набор: 9 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 пересылок.