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

Сортировки   18 марта 2012  Автор статьи:  

Быстрая сортировка(Quick Sort, QSort) — сортировка, основанная на сравнениях, широко используется на практике из-за быстрой работы в большинстве случаев. Эта сортировка не является стабильной, реализуется рекурсивно. В худшем случае работает за O(n^2).
QSort — классический пример принципа разделяй и властвуй.
QSort традиционно реализуется как функция, которой на вход подается массив a и значения l и r, удовлетворяющие условию: 0\le{l}\le{r}\le{n}, где n — длина массива. Вызов QSort(a,l,r) сортирует участок массива с индексами от l до r включительно. Для полной сортировки массива нужно вызвать QSort(a,0,n-1). Общий принцип работы Qsort следующий:

  1. Выбирается опорное значение x, равное x=a[i], где {l}\le{i}\le{r}
  2. С помощью индексов i и j массив а делится на три части: l\le{j}\le{i}\le{r}
    a)[l,i)содержит все элементы, меньше х
    б)[j,i)содержит все элементы, равные х
    в)[i,r]содержит все элементы, больше х
  3. Элементы средней части уже заняли свое относительное положение и для полной сортировки массива достаточно отдельно отсортировать левую и правую части, если в них более одного элемента

В зависимости от выбора опорного элемента, изменяется те входные последовательности, на которых алгоритм работает за O(n^2), поэтому используют различные подходы к выбору опорного элемента, основная цель которых — увеличить вероятность того, что левая и правая части будут разделены примерно поровну:

  1. x = a[\lfloor\frac{l+r}{2}\rfloor] — очень часто встречается «плохая» входная последовательность элементов
  2. x=a[l](x=a[r]) — аналогично предыдущему очень часто будет работать за O(n^2)
  3. x=a[random(l,r)] — очень маленькая вероятность долгого времени работы, однако из-за случайности выбора не используется в стандартных пакетах
  4. Особым образом выбрать три элемента массива, а потом взять средний из них(медиана из трех). Это наиболее устойчивый способ выбора опорного элемента.

Этап разделения массива на 3 части называется partition и может быть осуществлен за О(n). В предположении, что разделение массива на левую и правую части происходит примерно поровну, время работы алгоритма можно оценить с помощью следующей рекуррентной формулы: T(n) = 2T(n/2) + O(n). Несложно доказать, что T(n)=O(n log(n)).
Суммарное количество действий для фиксированной глубины рекурсии составит O(n), при разделении примерно поровну, максимальная глубина рекурсии составит logn(или \log_2{n}), а следовательно количество действий — nlog(n).
На самом деле, даже при разделении в пропорции 1:2, максимальная глубина рекурсии составит \log_{\frac{3}{2}}{n}=\frac{log_2{n}}{log_2{\frac{3}{2}}}=C\cdot\log_2{n}. Таким образом разделение в любой, но фиксированной пропорции приводит к логарифмической оценке максимальной глубины, но «равномерность» раздела влияет на величину константы.
Алгоритм этапа partition:

  1. Возьмем i=l и j=r
  2. Пока a[i] < x, увеличиваем индекс i на единицу.
  3. Пока a[j] > x, уменьшаем индекс j на единицу.
  4. Если i\le\j меняем значения a[i] и a[j] местами. Уменьшаем j на 1.Увеличиваем i на 1.
  5. Если i\le\j, возвращаемся к шагу 2 и продолжаем работу алгоритма, иначе разделение массива на три части по опорному элементу х завершено.

  • r04

    Добавь к исходникам реализацию быстрой сортировки на Prolog: http://pro-prof.com/archives/838 и Erlang: http://pro-prof.com/archives/872 , а-то тут только реализации на императивных языках….

    Кстати, у тебя тут описано, что массив делится на 3 части, в реализации на плюсах, части 2, я так понимаю (элементы, равные опорному не учитываются нигде). Если ты на вход своей программы подашь массив из 100 одинаковых элементов, то она сделает 300 с лишним перестановок. Хотя, я не особо представляю как делить массив на 3 части (особенно если опорный элемент брать из середины, а не с начала).

    • Ну на счет пролога и ерланга… Да я на них не пишу и никому в практических целях писать не советую, если только вы не решаете какую — то специфическую задачу. На счет трех частей, массив действительно делится на три части c l до j, с j до i, c i до r, где первую и последнюю часть мы сортируем, а центральная уже находится на нужном месте и отсортированна, так как все элементы в ней равны опорному. Ну если я подам массив из 100 одинаковых чисел, то у меня за 100 перестановок и отсортируется, так как рекурсия не будет выполнена ни разу, а будет выполнена только операция partion. На вопрос как делить массив на три части, на то и есть функция partion.

      • r04

        да, я затупил. Про пролог согласен, я попытался нам сервер написать, успехом проект не увенчался ) Но с эрлангом я еще экспериментирую, пока что не уверен что он не подходит для практических задач.

        • Переходи сразу к scala. Я бы его изучил, он следующий виток развития языков в целом, притом вроде как java — ориентированный.

          • r04

            Я почитаю, но поверхностный взгляд на scala не радует )
            я чето с трудом представляю как ООП замесить с функциональщиной.
            Visual Prolog новых версий тоже вон объектно-ориентирован не менее чем жаба, кому-то это даже нравится, как по мне — эпически все усложняет.

            В SWI и Erlang есть модули, и этого ИМХО (это мое неавторитетное мнение, я предупредил) более чем достаточно.
            Я не представляю как можно использовать ООП без побочных эффектов, а следовательно, не понимаю зачем это нужно в функциональных и логических языках.

          • Решил продублировать, а то ты что — то по почте не отвечаешь. На счет сотрудничества пишите на почту lordrp@bk.ru. У меня есть встречные предложения.

          • r04

            ответил на почту.
            ЗЫ. вот этот дискус позволяет тебе сообщения удалять? (всякий оффтоп, типа этого)

          • Да, и хранит сообщения притом на сервере дискаса, что снижает нагрузку на сервер сайта.

Научиться программировать

  • на Delphi

  • на Java

  • на C++