Сортировка с помощью дерева (Heapsort)

Сортировка разделением (Quicksort)

Сортировка выбором

При сортировке массива a[1], a[2], ..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 2.5.

Таблица 2.5. Пример сортировки простым выбором

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 1 23 5 65 44 33 8 6
Шаг 2 1 5 23 65 44 33 8 6
Шаг 3 1 5 6 65 44 33 8 23
Шаг 4 1 5 6 8 44 33 65 23
Шаг 5 1 5 6 8 33 44 65 23
Шаг 6 1 5 6 8 23 44 65 33
Шаг 7 1 5 6 8 23 33 65 44
Шаг 8 1 5 6 8 23 33 44 65

Для метода сортировки простым выбором требуемое число сравнений - nx(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(n?ln n), что в ряде случаев делает этот метод предпочтительным.

Метод сортировки разделением был предложен Чарльзом Хоаром (он любит называть себя Тони) в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследим этот процесс на примере нашего стандартного массива (таблица 2.6).

Таблица 2.6. Пример быстрой сортировки

Начальное состояние массива 8 23 5 65 |44| 33 1 6
Шаг 1 (в качестве x выбирается a[5]) |--------| 8 23 5 6 44 33 1 65 |---| 8 23 5 6 1 33 44 65
Шаг 2 (в подмассиве a[1], a[5] в качестве x выбирается a[3]) 8 23 |5| 6 1 33 44 65 |--------| 1 23 5 6 8 33 44 65 |--| 1 5 23 6 8 33 44 65
Шаг 3 (в подмассиве a[3], a[5] в качестве x выбирается a[4]) 1 5 23 |6| 8 33 44 65 |----| 1 5 8 6 23 33 44 65
Шаг 4 (в подмассиве a[3], a[4] выбирается a[4]) 1 5 8 |6| 23 33 44 65 |--| 1 5 6 8 23 33 44 65

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n?log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

Начнем с простого метода сортировки с помощью дерева, при использовании которого явно строится двоичное дерево сравнения ключей. Построение дерева начинается с листьев, которые содержат все элементы массива. Из каждой соседней пары выбирается наименьший элемент, и эти элементы образуют следующий (ближе к корню уровень дерева). Из каждой соседней пары выбирается наименьший элемент и т.д., пока не будет построен корень, содержащий наименьший элемент массива. Двоичное дерево сравнения для массива, используемого в наших примерах, показано на рисунке 2.1. Итак, мы уже имеем наименьшее значение элементов массива. Для того, чтобы получить следующий по величине элемент, спустимся от корня по пути, ведущему к листу с наименьшим значением. В этой листовой вершине проставляется фиктивный ключ с "бесконечно большим" значением, а во все промежуточные узлы, занимавшиеся наименьшим элементом, заносится наименьшее значение из узлов - непосредственных потомков (рис. 2.2). Процесс продолжается до тех пор, пока все узлы дерева не будут заполнены фиктивными ключами (рисунки 2.3 - 2.8).


Рис. 2.1.


Рис. 2.2. Второй шаг


Рис. 2.3. Третий шаг


Рис. 2.4. четвертый шаг


Рис. 2.5. Пятый шаг


Рис. 2.6. Шестой шаг


Рис. 2.7. Седьмой шаг


Рис. 2.8. Восьмой шаг

На каждом из n шагов, требуемых для сортировки массива, нужно log n (двоичный) сравнений. Следовательно, всего потребуется n?log n сравнений, но для представления дерева понадобится 2n - 1 дополнительных единиц памяти.

Имеется более совершенный алгоритм, который принято называть пирамидальной сортировкой (Heapsort). Его идея состоит в том, что вместо полного дерева сравнения исходный массив a[1], a[2], ..., a[n] преобразуется в пирамиду, обладающую тем свойством, что для каждого a[i] выполняются условия a[i] <= a[2i] и a[i] <= a[2i+1]. Затем пирамида используется для сортировки.

Наиболее наглядно метод построения пирамиды выглядит при древовидном представлении массива, показанном на рисунке 2.9. Массив представляется в виде двоичного дерева, корень которого соответствует элементу массива a[1]. На втором ярусе находятся элементы a[2] и a[3]. На третьем - a[4], a[5], a[6], a[7] и т.д. Как видно, для массива с нечетным количеством элементов соответствующее дерево будет сбалансированным, а для массива с четным количеством элементов n элемент a[n] будет единственным (самым левым) листом "почти" сбалансированного дерева.


Рис. 2.9.

Очевидно, что при построении пирамиды нас будут интересовать элементы a[n/2], a[n/2-1], ..., a[1] для массивов с четным числом элементов и элементы a[(n-1)/2], a[(n-1)/2-1], ..., a[1] для массивов с нечетным числом элементов (поскольку только для таких элементов существенны ограничения пирамиды). Пусть i - наибольший индекс из числа индексов элементов, для которых существенны ограничения пирамиды. Тогда берется элемент a[i] в построенном дереве и для него выполняется процедура просеивания, состоящая в том, что выбирается ветвь дерева, соответствующая min(a[2?i], a[2?i+1]), и значение a[i] меняется местами со значением соответствующего элемента. Если этот элемент не является листом дерева, для него выполняется аналогичная процедура и т.д. Такие действия выполняются последовательно для a[i], a[i-1], ..., a[1]. Легко видеть, что в результате мы получим древовидное представление пирамиды для исходного массива (последовательность шагов для используемого в наших примерах массива показана на рисунках 2.10-2.13).


Рис. 2.10.


Рис. 2.11.


Рис. 2.12.


Рис. 2.13.

В 1964 г. Флойд предложил метод построения пирамиды без явного построения дерева (хотя метод основан на тех же идеях). Построение пирамиды методом Флойда для нашего стандартного массива показано в таблице 2.7.

Таблица 2.7 Пример построения пирамиды

Начальное состояние массива 8 23 5 |65| 44 33 1 6
Шаг 1 8 23 |5| 6 44 33 1 65
Шаг 2 8 |23| 1 6 44 33 5 65
Шаг 3 |8| 6 1 23 44 33 5 65
Шаг 4 1 6 8 23 44 33 5 65 1 6 5 23 44 33 8 65

В таблице 2.8 показано, как производится сортировка с использованием построенной пирамиды. Суть алгоритма заключается в следующем. Пусть i - наибольший индекс массива, для которого существенны условия пирамиды. Тогда начиная с a[1] до a[i] выполняются следующие действия. На каждом шаге выбирается последний элемент пирамиды (в нашем случае первым будет выбран элемент a[8]). Его значение меняется со значением a[1], после чего для a[1] выполняется просеивание. При этом на каждом шаге число элементов в пирамиде уменьшается на 1 (после первого шага в качестве элементов пирамиды рассматриваются a[1], a[2], ..., a[n-1]; после второго - a[1], a[2], ..., a[n-2] и т.д., пока в пирамиде не останется один элемент). Легко видеть (это иллюстрируется в таблице 2.8), что в результате мы получим массив, упорядоченный в порядке убывания.

Таблица 2.8 Сортировка с помощью пирамиды

Исходная пирамида 1 6 5 23 44 33 8 65
Шаг 1 65 6 5 23 44 33 8 1 5 6 65 23 44 33 8 1 5 6 8 23 44 33 65 1
Шаг 2 65 6 8 23 44 33 5 1 6 65 8 23 44 33 5 1 6 23 8 65 44 33 5 1
Шаг 3 33 23 8 65 44 6 5 1 8 23 33 65 44 6 5 1
Шаг 4 44 23 33 65 8 6 5 1 23 44 33 65 8 6 5 1
Шаг 5 65 44 33 23 8 6 5 1 33 44 65 23 8 6 5 1
Шаг 6 65 44 33 23 8 6 5 1 44 65 33 23 8 6 5 1
Шаг 7 65 44 33 23 8 6 5 1

Процедура сортировки с использованием пирамиды требует выполнения порядка nxlog n шагов (логарифм - двоичный) в худшем случае, что делает ее особо привлекательной для сортировки больших массивов.