Алгоритмы внутренней сортировки

Одной из наиболее распространённых компьютерных операций является сортировка, т.е. размещение элементов коллекции в определенном порядке. Программист должен уметь выбирать и использовать различные алгоритмы сортировки: от простых, для небольших по размеру коллекций, до высокоэффективных алгоритмов для коллекций с большого объёма.

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

Существует множество методов внутренней сортировки, среди которых выделяются три элементарных метода, от которых произошли многие другие, более эффективные методы сортировки. Это сортировка методом выбора, методом вставок и обменная сортировка [2, 3, 5, 7]. Эти простейшие методы сортировки обладают низкой эффективностью и имеют трудоёмкость O(n ² ). Рекомендуется использовать эти алгоритмы для коллекций небольшого размера.

От этих трех методов произошли многое усовершенствованные методы сортировки, достигающие большей эффективности для больших объёмов данных. Производными от сортировки выбором являются сортировка с помощью дерева выбора [1] и пирамидальная сортировка [3, 6, 8]. Эти методы используют выбор минимального элемента массива с помощью вспомогательной структуры – дерева выбора или частично упорядоченного дерева (пирамиды) соответственно. Ниже приведены примеры дерева выбора и пирамиды для набора 14 34 1 32 7 56 2 10 5.

Рис.3 Структура сортирующих деревьев.

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

Наиболее известным методом, производным от сортировки методом вставок, является сортировка Шелла [2, 5, 7]. Основная идея этого метода заключается в том, чтобы ускорить упорядочение за счет перемещения элементов при вставках на большие расстояния в массиве. Для этого в массиве выделяются группы элементов, отстоящих друг от друга с первоначально большим шагом h. В каждой группе выполняется сортировка методом вставок. Затем шаг h уменьшается, выделяются новые группы элементов, отстоящих друг от друга с уменьшенным шагом, и вновь выполняется сортировка групп методом вставок. Уменьшение шага и выделение новых подгрупп продолжается, пока шаг не уменьшится до единицы. На последнем этапе выполняется сортировка методом вставок всего массива. Поскольку на предыдущих этапах при сортировке подгрупп массив был значительно упорядочен, на последнем этапе число перестановок в массиве будет незначительным.

Ниже приведена схема сортировки массива методом Шелла.

Рис.4 Схема сортировки методом Шелла.

Для увеличения эффективности сортировки Шелла предлагаются правила для уменьшения шага h. Широко известна последовательность Кнута [5], использование которой повышает эффективность сортировки Шелла до оценки О(n ^3/2 ). Она имеет вид 1, 4, 13, 40, 121 364, 1093, 3280, 9841. Шаги находятся в соотношении h_k = 3 h_k+1+1.

Есть другие последовательности шагов [8], дающих хорошую эффективность, например: 1, 8, 23, 77, 281, 1073, 4193, 16577,, т.е. последовательность 4ⁱ⁺¹ + 3 2ⁱ + 1 для i 0. Эта последовательность обеспечивает хорошую эффективность для самых трудных случаев сортировки – О(n ^4/3 ). Приведенные последовательности эффективны в силу того, что шаги взаимно просты.

Сортировка разделением (быстрая сортировка) [1–3, 5-8] является улучшением обменной сортировки и в настоящее время признана, как самый эффективный метод сортировки для больших объёмов данных. Трудоёмкость быстрой сортировки имеет нотацию O(n log ₂ n). Идея улучшения метода та же, что и в сортировке Шелла – увеличение расстояния при обменах местами элементов. Благодаря этому элементы быстрее занимают правильные позиции в упорядочиваемом массиве. Метод быстрой сортировки действует по схеме разделения задач на подзадачи. Массив разделяется на две части относительно некоторого опорного элемента. Затем разделение выполняется для каждой из этих частей и так далее до тех пор, пока размер каждой части не станет равным 1. По окончании этого процесса массив отсортирован. Схема разделения методом быстрой сортировки показана на рис. 5

Рис.5 Схема сортировки методом разделения (быстрой сортировки).

Сортировка методом слияния аналогична такому же методу, предназначенному для упорядочивания внешних файлов[2, 3, 8]. Также как и быстрая сортировка, метод действует по схеме нисходящего разделения массива на части. Первоначальный массив разделяется на две равные части, затем выполняется деление частей на две равные части и так далее, пока не будут получены части из одного элемента. Затем выполняется восходящее слияние смежных в массиве частей в упорядоченные части по два элемента, по четыре элемента и так далее, пока при слиянии не будет получена часть, соответствующая по размеру всему массиву. Схема сортировки разделения методом слияния показана на рис. 6.

Рис.6 Схема сортировки методом слияния.

Выше была описана сортировка слиянием с нисходящим разбиением массива на части. Поэтому она получила наименование «нисходящая сортировка слиянием». Существует альтернативная схема сортировки слиянием - «восходящая сортировка». Она исключает первоначальный этап нисходящего разделения массива на части и считает каждый элемент массива частью, готовой к слиянию с соседней частью. То есть, сортировка сразу начинается с восходящего слияния упорядоченных частей из одного, двух и так далее элементов.

Независимо от схемы сортировки слиянием оба альтернативных метода имеют оценку трудоёмкости O(n log ₂ n).

Поразрядная (карманная) сортировка [3,4,8,11]основана на поэтапном распределении сортируемых значений с одинаковым значением текущего разряда по отдельным «карманам». Для этого алгоритм поразрядной сортировки рассматривает значения в массиве, как числа, представленные в позиционной системе счисления с основанием R и работает на каждом этапе с отдельным разрядом - цифрой. Различают две схемы выборки текущей цифры из сортируемых значений. MSD-сортировка (Most Significant Digit radix sort) анализирует цифры значений слева направо, начиная с наиболее значащих цифр. LSD-сортировка (Last Significant Digit radix sort) анализирует цифры в значениях справа налево, начиная с младших цифр. Сортировка заканчивается, когда будет выполнено распределение значений по последней цифре.

Ход MSD-сортировки аналогичен быстрой сортировке с разделением массива на части и дальнейшим рекурсивным разделением частей. На первом этапе значения в массиве распределяются по карманам в соответствием со значением старшей цифры. В свою очередь к карманам рекурсивно применяется распределение по следующей цифре и так далее, пока не будет выполнено распределение по младшей цифре. Пример MSD-сортировки приведён ниже. На рисунке не показаны пустые карманы, в которые не попало ни одно значение. Общее количество карманов равно количеству возможных значений цифры, т.е. основанию системы счисления R.

Рис. 7. Схема поразрядной десятичной MSD-сортировки

Трудоёмкость MSD-сортировки оценивается величиной O(n log _R n). При R=2 трудоёмкость сопоставима с трудоёмкостью быстрой сортировки или сортировки слиянием и равна O(n log ₂ n). При больших R величина log _R n становится малой и трудоёмкость становится линейной функцией O(n).

LSD-сортировка выбирает цифры из сортируемых значений в направлении справа налево. В отличие от MSD-сортировки, алгоритм LSD-сортировки не рекурсивный. На каждом этапе значения распределяются по карманам в соответствии со значением очередного разряда-цифры. Сложившееся распределение по карманам формирует новое содержимое сортируемого массива. На следующем этапе массив вновь распределяется по карманам по значению следующего разряда-цифры и т.д. Сортировка заканчивается, когда будет выполнено распределение по старшей цифре. Схема LSD-сортировки представлена на рисунке 8.

012 3 215 4 022 2 000 4 028 3 156 0 106 1 215 0

[156 0 215 0 ] [106 1 ] [022 2 ] [012 3 028 3 ] [215 4 000 4 ]

15 6 0 21 5 0 10 6 1 02 2 2 01 2 3 02 8 3 21 5 4 00 0 4

[00 0 4] [02 2 2 01 2 3] [21 5 0 21 5 4] [15 6 0 10 6 1] [02 8 3]

0 0 04 0 2 22 0 1 23 2 1 50 2 1 54 1 5 60 1 0 61 0 2 83

[0 0 04 1 0 61] [0 1 23 2 1 50 2 1 54] [0 2 22 0 2 83] [1 5 60]

0 004 1 061 0 123 2 150 2 154 0 222 0 283 1 560

[ 0 004 0 123 0 222 0 283] [ 1 061 1 560] [ 2 150 2 154]

0004 0123 0222 0283 1061 1560 2150 2154

Рис. 8. Схема поразрядной десятичной LSD-сортировки

Трудоёмкость LSD-сортировки имеет нотацию O(n w), где w – число разрядов в сортируемых значениях. То есть трудоёмкость LSD-сортировки линейно зависит от объёма сортируемых данных.

---

Дата добавления: 2015-11-04