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

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

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

Общее описание[править | править вики-текст]

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

Общая идея алгоритма состоит в следующем:

  • Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
  • Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом — «меньшие опорного», «равные» и «большие». [1]
  • Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

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

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

Алгоритм[править | править вики-текст]

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

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

Оценка сложности алгоритма[править | править вики-текст]

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

Лучший случай.
В наиболее сбалансированном варианте при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит \log_2 n. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C_n = 2 \cdot C_{n/2} + n, что даёт общую сложность алгоритма O(n \cdot \log_2 n).
Среднее.
Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно.
Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна \log_{4/3} n, а это по-прежнему даёт сложность O(n \log n). Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами.
Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива.
Удачное разделение даёт глубину рекурсии не более \log_{4/3} n. Поскольку вероятность удачи равна 0,5, для получения k удачных разделений в среднем потребуется 2 \cdot k рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит 2 \cdot \log_{4/3} n, что равно O(\log n) А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O(n) операций, средняя сложность составит O(n \log n).
Худший случай.
В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и n-1, то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется n-1 операций разделения, а общее время работы составит \textstyle\sum_{i=0}^n (n-i) = O(n^2) операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

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

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

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

Недостатки:

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

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

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

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

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

  • Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
  • Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
  • Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор — практически неосуществимым. Ожидаемое время выполнения алгоритма сортировки составляет O(n lg n).

Недостаток всех усложнённых методов выбора опорного элемента — дополнительные накладные расходы; впрочем, они не так велики.

Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:

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

Реализация[править | править вики-текст]

Множество примеров реализации алгоритма (включая полностью нерекурсивный) можно найти в WikiBooks по приведённой ссылке. В данном разделе приводится лишь пара примеров наиболее типичной реализации на процедурном (Pascal) и функциональном (Erlang) языках.

// Реализация на языке pascal
// Если раскомментировать строки кода, начинающиеся с "//",
// то получится реализация с одной рекурсивной ветвью, в которой
// меньшая часть разделённого массива сортируется рекурсивным вызовом,
// а бо'льшая - в цикле, что гарантирует глубину рекурсии не более lg(N).
procedure qSort(var ar: array of real);
  // Вложенная функция сортировки для рекурсивного вызова
  // Нужна, чтобы не передавать в вызов основной функции границы массива
  procedure sort(var ar: array of real; low, high: integer);
  var i, j: integer;
      m, wsp: real;
  begin
    // repeat
      i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента
      repeat
        while ar[i]<m do Inc(i);    // изменить порядок сортировки можно
        while ar[j]>m do Dec(j);    // поменяв >< в этих двух строках 
        if i<=j then begin
          wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp;
          Inc(i); Dec(j);
         end;
      until i>j;
    // if (j - low) < (high - i) then begin 
      if low<j then sort(ar, low, j);
    // low := i;
    //   end 
    // else begin
      if i<high then sort(ar, i, high);
    // high := j;
    // end; 
    //until low = high;
  end;
begin
  sort(ar, 0, High(ar));
end;
%% алгоритм на языке Erlang
qsort([]) -> [];
qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

Примечания[править | править вики-текст]

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

Литература[править | править вики-текст]

  • Ананий В. Левитин Глава 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

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

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