Быстрая сортировка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Анимированная схема алгоритма

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в МГУ в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Содержание

Краткое описание алгоритма [править]

  • выбрать элемент, называемый опорным.
  • сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
  • повторить рекурсивно для «меньших» и «больших».

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

Алгоритм [править]

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

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
    2. Вычисляется индекс опорного элемента m.
    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
    6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

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

  //алгоритм на языке java 
  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 <= j){           
              // обмен элементов местами:
              int temp = A[i];
              A[i] = A[j];
              A[j] = temp;
              // переход к следующим элементам:
              i++; j--;
          }
      } while(i < j);
      if(low < j) qSort(A, low, j);
      if(i < high) qSort(A, i, high);
  }
// Алгоритм на языке C/C++
// Вариант реализации быстрой сортировки наподобие qsort из стандартной библиотеки
 
typedef int (*PTF)(const void *, const void *);
 
void qqsort(void* base, size_t n, size_t sz, PTF cmp)
{
    if (n <= 1)
    {
        return;
    }
 
    char* b = (char*)base;
    char* bm = b + (n/2)*sz;
    char* tm = (char*)malloc(sizeof(char)*sz);
 
    // Скопируем в "буфер" центральный элемент.
    for (int k = 0; k < sz; ++k)
    {
        tm[k] = bm[k];
    }
 
    char* lb = b; // Вычислим адрес крайнего левого элемента.
    char* rb = b + (n-1)*sz; // Вычислим адрес крайнего правого элемента.
 
    while (lb < rb)
    {
        while (cmp(tm, lb) > 0)
        {
            lb += sz;
        }
        while (cmp(tm, rb) < 0)
        {
            rb -= sz;
        }
        if (lb < rb)
        {
            // Переместим элементы.
            for (int k = 0; k < sz; ++k)
            {
                char tmp = lb[k];
                lb[k] = rb[k];
                rb[k] = tmp;
            }
            lb += sz;
            rb -= sz;
        }
        else if (lb == rb)
        {
            lb += sz;
            rb -= sz;
        }
    }
 
    free(tm);
    qqsort(b, (rb - b)/sz + 1, sz, cmp);
    qqsort(lb, ((b + n*sz) - b)/sz - (lb - b)/sz, sz, cmp);
}
//алгоритм на языке pascal
//при первом вызове 2-ой аргумент должен быть равен 0
//3-ий аргумент должен быть равен числу элементов массива - 1
procedure qSort(var ar: array of real; low, high: integer);
var i, j: integer;
    m, wsp: real;
begin
  i:=low;
  j:=high;
  m:=ar[(i+j) div 2];
  repeat
    while ar[i]<m do Inc(i); //Инкремент i. Эквивалентно коду i:=i+1, но компилируется оптимальнее
    while ar[j]>m do Dec(j); //Декремент j. Эквивалентно коду j:=j-1;
    if i<=j then begin
      wsp:=ar[i];
      ar[i]:=ar[j];
      ar[j]:=wsp;
      Inc(i);
      Dec(j);
    end;
  until i>j;
  if low<j then qSort(ar, low, j);
  if i<high then qSort(ar, i, high);
end;


//алгоритм на языке Visual Basic
//при первом вызове 2-ой аргумент должен быть равен 1 (или 0, в зависимости от базы)
//3-ий аргумент должен быть равен числу элементов массива (или числу элементов массива - 1, если база = 0) 
Sub qSort(ByRef ar() As Double, ByVal low As Integer, ByVal high As Integer)
        Dim i, j As Integer
        Dim m, wsp As Double
        i = low
        j = high
        m = ar((i + j) \ 2)
        Do Until i > j
            Do While ar(i) < m
                i = i + 1
            Loop
 
            Do While ar(j) > m
                j = j - 1
            Loop
            If i <= j Then
                wsp = ar(i)
                ar(i) = ar(j)
                ar(j) = wsp
                i = i + 1
                j = j - 1
            End If
        Loop
        If low < j Then Call qSort(ar, low, j)
        If i < high Then Call qSort(ar, i, high)
    End Sub
%% алгоритм на языке Erlang
qsort([]) -> [];
qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

Оценка эффективности [править]

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.

  • Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения 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 худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Улучшения [править]

  • При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n lg n).
  • Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
  • Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log2n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
  • Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).

Достоинства и недостатки [править]

Достоинства:

  • Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
  • Прост в реализации.
  • Требует лишь O(\lg n) дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае O(n) памяти)
  • Хорошо сочетается с механизмами кэширования и виртуальной памяти.
  • Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.
  • Работает на связанных списках и других структурах с последовательным доступом.

Недостатки:

  • Сильно деградирует по скорости (до \Theta(n^2)) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.
  • Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать O(n) вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит O(\lg n).
  • Неустойчив — если требуется устойчивость, приходится расширять ключ.

Примечания [править]

Литература [править]

  • Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 174-179. — ISBN 5-8459-0987-2
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 198-219. — ISBN 5-8459-0857-4

См. также [править]

Ссылки [править]