.
БЫСТРАЯ СОРТИРОВКА(QuickSort)
Краткое описание
алгоритма
- выбрать элемент, называемый опорным.
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
- повторить рекурсивно для «меньших» и «больших».
Алгоритм
Быстрая сортировка использует
стратегию «разделяй и властвуй».
Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
- Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
- Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
- Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
- Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
- Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации
(на каждом следующем уровне рекурсии) длина обрабатываемого
отрезка массива уменьшается, по меньшей
мере, на единицу, терминальная ветвь рекурсии
будет достигнута всегда и обработка гарантированно
завершится.
Реализация алгоритма
на языке Java.
public static void qSort(int[] a, int low, int high)
{
int i = low;
int j = high;
int x = a[(low + (high-low)/2)];
do {
while (a[i] < x)
++i;
while (x < a[j])
--j;
if ( i <= j ) {
if( i < j ) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
++i;
--j;
}
} while (i <= j);
if (low < j)
qSort(a, low, j);
if (i < high)
qSort(a, i, high);
}
Вычислительная сложность
«быстрой» сортировки
Общий анализ эффективности «быстрой»
сортировки достаточно труден. Будет
лучше показать ее вычислительную сложность,
подсчитав число сравнений при некоторых
идеальных допущениях. Допустим, что n
– степень двойки, n = 2k (k = log2n),
а центральный элемент располагается
точно посередине каждого списка и разбивает
его на два подсписка примерно одинаковой
длины.
При первом сканировании
производится n-1 сравнений. В результате создаются
два подсписка размером n/2. На следующей
фазе обработка каждого подсписка требует
примерно n/2 сравнений. Общее число сравнений
на этой фазе равно 2(n/2) = n. На следующей
фазе обрабатываются четыре подсписка,
что требует 4(n/4) сравнений, и т.д. В конце
концов процесс разбиения прекращается
после k проходов, когда получившиеся подсписки
содержат по одному элементу. Общее число
сравнений приблизительно равно:
n + 2(n/2) + 4(n/4) + ... + n(n/n) = n + n + ... + n = n * k = n *
log2n
Для списка общего вида вычислительная
сложность «быстрой» сортировки
равна O(n log2 n). Идеальный случай, который
мы только что рассмотрели, фактически
возникает тогда, когда массив уже отсортирован
по возрастанию. Тогда центральный элемент
попадает точно в середину каждого подсписка.
Если массив отсортирован
по убыванию, то на первом проходе центральный элемент обнаруживается
на середине списка и меняется местами
с каждым элементом как в первом, так и
во втором подсписке. Результирующий список
почти отсортирован, алгоритм имеет сложность
порядка O(n log2n).
Наихудшим сценарием
для «быстрой» сортировки будет тот, при котором центральный
элемент все время попадает в одноэлементный
подсписок, а все прочие элементы остаются
во втором подсписке. Это происходит тогда,
когда центральным всегда является наименьший
элемент. Рассмотрим последовательность
3, 8, 1, 5, 9.
На первом проходе
производится n сравнений, а больший подсписок содержит
n-1 элементов. На следующем проходе этот
подсписок требует n-1 сравнений и дает
подсписок из n-2 элементов и т.д. Общее
число сравнений равно:n + n-1 + n-2 + ... + 2 = n(n+1)/2
- 1
Сложность худшего случая
равна O(n2), т.е. не лучше, чем для сортировок
вставками и выбором. Однако этот случай
является патологическим и маловероятен
на практике. В общем, средняя производительность
«быстрой» сортировки выше, чем у всех
рассмотренных нами сортировок.
Улучшения
- При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n lg n).
- Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
- Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log2n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
- Разбивать массив не на две, а на три части.
Достоинства и недостатки
Достоинства:
- Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
- Прост в реализации.
- Требует лишь O(lg n) дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае O(n) памяти)
- Хорошо сочетается с механизмами кэширования и виртуальной памяти.
- Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.
Недостатки:
- Сильно деградирует по скорости (до Θ(n2)) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.
- Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать O(n) вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит O(lg n).
- Неустойчив — если требуется устойчивость, приходится расширять ключ.