Быстрая сортировка — упорядочение за среднее время о(n log n).

      Комментарии к записи Быстрая сортировка — упорядочение за среднее время о(n log n). отключены

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы (Алгоритм, приведённый ниже, неверен: если в массиве оказалось два элемента, равных опорному и индексы l и r достигли их одновременно, то шаг 2.6 не изменяет массива при обмене этих элементов и алгоритм оказывается в вечном цикле. В англоязычной версии статьи приведён правильно действующий псевдо-код):

Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

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

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

Вычисляется индекс опорного элемента m.

Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

Если lr — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.

Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

public static void qSort(int[] A, int low, int high) {

int i = low;

int j = high;

int x = A[(low+high)/2]; // x — опорный элемент посредине между low и high

do {

while(A[i]x) ++i; // поиск элемента для переноса в старшую часть

while(A[j]x) —j; // поиск элемента для переноса в младшую часть

if(i

// обмен элементов местами:

int temp = A[i];

A[i] = A[j];

A[j] = temp;

// переход к следующим элементам:

i++; j—;

}

} while(ij);

if(lowj) qSort(A, low, j);

if(ihigh) qSort(A, i, high);

}

Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.

Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.

Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n?) обменов. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Статьи к прочтению:

Алгоритмы поиска и сортировки: Быстрая сортировка Хоара. Центр онлайн-обучения «Фоксфорд»


Похожие статьи:

  • Быстрая сортировка (хоара)

    Лабораторная работа №1 Методы сортировки Цель работы Цель данной работы: изучить различные методы сортировки; научиться проводить сравнительный анализ…

  • Анализ эффективности быстрой сортировки

    В среднем число операций порядка N?log2N, остальные сортировки в среднем N2 операций. Преимущество быстрой сортировки проявляется при больших N. Она…