Pull to refresh

Быстрая сортировка и с чем её едят

Lumber room
Awaiting invitation
Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort — это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

  1. Выбираем опорный элемент
  2. Разбиваем массив на 3 части
    • Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
    • Увеличиваем l, пока l-й элемент меньше опорного
    • Уменьшаем r, пока r-й элемент больше опорного
    • Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
    • Если l вдруг становится больше r, то прерываем цикл
  3. Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем!
void qsort (int b, int e)
{
  int l = b, r = e;
  int piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
  while (l <= r)
  {
    while (arr[l] < piv)
      l++;
    while (arr[r] > piv)
      r--;
    if (l <= r)
      swap (arr[l++], arr[r--]);
  }
  if (b < r)
    qsort (b, r);
  if (e > l)
    qsort (l, e);
}    /* ----- end of function qsort ----- */

// qsort (0, n-1);

* This source code was highlighted with Source Code Highlighter.

Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

Писáл сам, изредка поглядывая на
Википедию. Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!
Tags:
Hubs:
You can’t comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.