Материал: Глава 14. Алгоритмы сортировки
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
16
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 2 n)/6.
Отсюда следует, что данный метод неэффективен при малых n (десятки или сотни элементов), но с ростом n его эффективность резко растет, и при очень больших n метод дает наилучшие показатели среди всех универсальных методов сортировки.
К сожалению, есть одна ситуация, когда быстрая сортировка теряет свою эффективность и становится пропорциональной n2, т.е. опускается до уровня простых методов. Эта ситуация связана с правилом выбора опорного элемента. Эффективность метода сильно зависит от выбора опорного элемента, и использование простейшего способа выбора (серединный элемент массива) часто приводит к падению эффективности метода. Это связано с тем,
что каждое разделение массива на две половины в идеале должно давать
примерно равное число элементов слева и справа от опорного элемента
(принцип дихотомии!). Если опорный элемент близок к минимальному или максимальному, после попарных перестановок будут получены существенно неравномерные наборы. Если подобная ситуация возникает на каждом шаге работы алгоритма, общая эффективность резко падает. Для устранения этого
недостатка надо уметь правильно выбирать опорный элемент. 17
Наилучшее правило выбора опорного элемента – это так называемая
медиана. Медиана – это средний элемент массива не по расположению, а по
значению. В приведенном выше примере медианой является число 25,
которое также было и серединным элементом (честно говоря, пример был подобран специально). К сожалению, поиск медианы в массиве является задачей, сопоставимой по трудоемкости с самой сортировкой, поэтому были предложены другие, более простые правила выбора опорного элемента.
На практике хорошо показал себя следующий способ: выбрать случайно в массиве три элемента и взять в качестве опорного средний из них. Этот способ очень прост в реализации, т.к. требует только двух сравнений, но,
конечно, он может обеспечивать хорошие показатели только в среднем, и не гарантирует идеальное поведение алгоритма абсолютно для ЛЮБЫХ входных данных.
Что касается программной реализации базового алгоритма, то можно заметить его принципиальную особенность: разделение массива на 2
половины, разделение каждой половины на свои половины и т.д. При каждом разделении приходится запоминать правую половину (конечно, не сами элементы, а лишь индексы левой и правой границы) и возвращаться к ней после полной обработки левой половины. Все это как нельзя лучше соответствует рекурсивному принципу обработки, и поэтому быстрая сортировка проще всего реализуется рекурсивно.
Пример программной реализации метода быстрой сортировки представлен в листинге 14.5.
|
Листинг 14.5 – Метод быстрой сортировки |
|
|
|
|
1 |
void QuickSort(int[] array, int a, int b) |
|
2 |
{ |
|
3 |
int i = a; |
|
4 |
int j = b; |
|
5 |
int middle = array[( a + b )/2]; |
|
6 |
while(i <= j) |
|
7 |
{ |
|
8 |
while(array[i] < middle) |
|
|
18 |
|
9 |
{ |
10 |
i++; |
11 |
} |
12 |
while(array[j] > middle) |
13 |
{ |
14 |
j--; |
15 |
} |
16 |
if(i <= j) |
17 |
{ |
18 |
int temporaryVariable = array[i]; |
19 |
array[i] = array[j]; |
20 |
array[j] = temporaryVariable; |
21 |
i++; |
22 |
j--; |
23 |
} |
24 |
} |
25 |
if (a < j) |
26 |
{ |
27 |
QuickSort(array, a, j); |
28 |
} |
29 |
if (i < b) |
30 |
{ |
31 |
QuickSort(array, i, b); |
32 |
} |
33 |
} |
§14.7 Улучшенные методы сортировки: поразрядная сортировка
Пусть известно, что каждый ключ является k–разрядным целым числом. Например, если k = 4, то все ключи находятся в диапазоне 0000 – 9999. Смысл поразрядной сортировки заключается в том, что k раз повторяется карманная сортировка. На первом шаге все ключи группируются по младшей цифре (разряд единиц). Для этого в каждом ключе выделяется младшая цифра и элемент помещается в соответствующий список-карман для данной цифры. Потом все списки объединяются и создается новый массив, в
котором элементы упорядочены по младшей цифре ключа. К этому массиву опять применяется карманная сортировка, но уже по более старшей цифре
(разряд десятков): в каждом ключе выделяется вторая справа цифра и элементы распределяются по соответствующим спискам. Потом списки
19
объединяются в массив, где элементы будут упорядочены уже по двум младшим цифрам. Процесс распределения по все более старшим цифрам с последующим объединением повторяется до старшей цифры (разряд k).
Поскольку цифр всего 10, то для реализации метода необходим вспомогательный массив из 10 ячеек для хранения адресов соответствующих списков.
Пример. Пусть имеется исходный набор из 15-ти двухразрядных ключей
(k=2):
56, 17, 83, 09, 11, 27, 33, 02, 16, 45, 08, 37, 66, 99, 90
Первый шаг: выделяем младшую цифру и распределяем ключи по
десяти спискам:
ключ 56 в список для цифры 6, ключ 17 в список для цифры 7, …, ключ 16
опять в список для цифры 6 и т.д.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
8 |
9 |
|
|
|
|
|
|
|
|
|
|
|
90 |
11 02 83 |
|
45 |
56 |
17 08 |
09 |
||||
|
|
|
33 |
|
|
16 |
27 |
|
|
99 |
|
|
|
|
|
|
66 |
37 |
|
|
|
Объединяем списки: 90, 11, 02, 83, 33, 45, 56, 16, 66, 17, 27, 37, 08, 09, 99
В этом наборе ключи упорядочены по младшей цифре
Второй шаг: выделяем старшую цифру (десятки) и распределяем ключи по своим спискам:
ключ 90 в список для 9, ключ 11 в список для 1, ключ 02 в список для 0 и т.д.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
|
02 |
11 |
27 33 45 |
56 66 |
|
83 |
90 |
|||
08 |
16 |
|
37 |
|
|
|
|
|
99 |
09 |
17 |
|
|
|
|
|
|
|
|
Объединение этих списков дает отсортированный набор:
02, 08, 09, 11, 16, 17, 27, 33, 37, 45, 56, 66, 83, 90, 99
20