Пример работы быстрой сортировки
Имеется массив данных: 34, 17, 45, 9, 6, 18, 12, 14, 37, 49, 5. Его необходимо отсортировать по возрастанию (табл. 13.1). Разобьём для этого массив на две части и выберем элемент x равный 18. Выберем из левой части первый элемент, который больше 18 – это 34, а из правой части элемент, который меньше 18 – это 5. Поменяем их местами и получим новую последовательность: 5, 17, 45, 9, 6, 18, 12, 14, 37, 49, 34. Далее процесс повторяется (см. Таблицу 13.1).
Таблица 13.1
Пример работы быстрой сортировки на примере
Шаг |
Последовательность элементов |
X |
Меняем |
1 |
34, 17, 45, 9, 6, 18, 12, 14, 37, 49, 5 |
18 |
34 и 5 |
2 |
5, 17, 45, 9, 6, 18, 12, 14, 37, 49, 34 |
18 |
45 и 14 |
3 |
5, 17, 14, 9, 6, 18, 12, 45, 37, 49, 34 |
18 |
12 |
4 |
5, 17, 14, 9, 6, 12, 18, 45, 37, 49, 34 |
14 |
17 и 12 |
5 |
5, 12, 14, 9, 6, 17, 18, 45, 37, 49, 34 |
14 |
6 |
6 |
5, 12, 6, 14, 9, 17, 18, 45, 37, 49, 34 |
14 |
9 |
7 |
5, 12, 6, 9, 14, 17, 18, 45, 37, 49, 34 |
12 |
9 |
8 |
5, 9, 12, 6, 14, 17, 18, 45, 37, 49, 34 |
12 |
6 |
9 |
5, 9, 6, 12, 14, 17, 18, 45, 37, 49, 34 |
9 |
6 |
10 |
5, 6, 9, 12, 14, 17, 18, 45, 37, 49, 34 |
5, 37 |
-, 45 и 34 |
11 |
5, 6, 9, 12, 14, 17, 18, 34, 37, 49, 45 |
49 |
45 |
12 |
5, 6, 9, 12, 14, 17, 18, 34, 37, 45, 49 |
|
|
Блок-схема быстрой сортировки
Если индекс выбранного x равен i, то он делит массив сначала на две части: 1) a[1],....,a[i-1] и 2) a[j+1],...,a[n], где j = i+1 для текущего случая. Потом разделение аналогичным образом повторяется. Описанные ниже блок-схемами алгоритмы просты и эффективны, так как сравниваемые переменные i, j и x можно хранить во время просмотра в быстрых регистрах процессора. Здесь применяется процесс разделения к получившимся двум частям, затем к частям частей, и так далее до тех пор, пока каждая из частей не будет состоять из одного единственного элемента. Процедура sort реализует разделение массива на две части, и рекурсивно обращается сама к себе (рис. 13.1). Данная процедура sort(m,l) описывается и вызывается в процедуре hoarsort (рис. 13.2), которая потом вызывается в программе таким образом: hoarsort(b, n), где b – это отсортированный массив, а – это число элементов в массиве.
Существуют и другие способы реализации процедуры sort(m,l), которые могут значительно сократить код программы и уменьшить число используемых переменных.
