Быстрая сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Разбиение массива)
(→‎Разбиение массива)
Строка 29: Строка 29:
  
 
===Разбиение массива===
 
===Разбиение массива===
−
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> нужным образом.
+
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа T нужным образом.
 
Разбиение осуществляется с использованием следующей стратегии. Прежде всего,  
 
Разбиение осуществляется с использованием следующей стратегии. Прежде всего,  
 
в качестве разделяющего элемента произвольно выбирается элемент  
 
в качестве разделяющего элемента произвольно выбирается элемент  
Строка 54: Строка 54:
 
справа от v и ни одного меньшего элемента слева от v.
 
справа от v и ни одного меньшего элемента слева от v.
  
−
   '''int''' partition(a: '''int'''[n], '''int''' l, '''int''' r)
+
   '''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)
−
       v = a[r]
+
       '''T''' v = a[r]
−
       i = l
+
       '''int''' i = l
−
       j = r - 1
+
       '''int''' j = r - 1
 
       '''while''' ''true''  
 
       '''while''' ''true''  
 
         '''while''' (a[i] < v)
 
         '''while''' (a[i] < v)

Версия 23:14, 16 июня 2016

Быстрая сортировка (англ. quick sort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(n\log{n})[/math], что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из [math]n[/math] элементов в худшем случае может составить [math]\Theta(n^2)[/math], на практике этот алгоритм является одним из самых быстрых.

Алгоритм

Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Как будет показано далее, точное положение точки деления зависит от исходного порядка элементов во входном файле. Суть метода заключается в процессе разбиения файла, который переупорядочивает файл таким образом, что выполняются следующие условия: ¦ Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве. ¦ Ни один из элементов a[i],..., a[i-l] не пре- вышает a[i]. м Ни один из элементов a[i+l],..., а[г] не явля- ется меньшим a[i].


  • Массив [math] a[l \ldots r][/math] разбивается на два (возможно пустых) подмассива [math] a[l \ldots q-1][/math] и [math] a[q+1 \ldots r][/math], таких, что каждый элемент [math] a[l \ldots q-1][/math] меньше или равен [math] a[q][/math], который в свою очередь, не превышает любой элемент подмассива [math] a[q+1 \ldots r][/math]. Индекс вычисляется в ходе процедуры разбиения.
  • Подмассивы [math] a[l \ldots q-1][/math] и [math] a[q+1 \ldots r][/math] сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
  • Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив [math] a[l \ldots r][/math] оказывается отсортированным.

Псевдокод

  void quicksort(a: int[n], int l, int r)
     if l < r
        q = partition(a, l, r)
        quicksort(a, l, q - 1)
        quicksort(a, q + 1, r)

Для сортировки всего массива необходимо выполнить процедуру [math]\mathrm{quicksort(a, 0, length[a] - 1)}[/math].

Разбиение массива

Основной шаг алгоритма сортировки — процедура [math]\mathrm{partition}[/math], которая переставляет элементы массива [math]a[l \ldots r][/math] типа T нужным образом. Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[г] — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден эле- мент, превосходящий по значению разделяющий элемент, затем выполняется про- смотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разде- ленном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Переменная v сохраняет значение разделяющего элемента a[r], a i и j представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение i и уменьшает значение j на 1, причем условие, что ни один элемент слева от i не больше v и ни один элемент справа от j не меньше v, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершает- ся, меняя местами а[г] и a[i], при этом v присваивается зна- чение a[i], так что не будет ни одного большего элемента справа от v и ни одного меньшего элемента слева от v. 

  int partition(a: T[n], int l, int r)
     T v = a[r]
     int i = l
     int j = r - 1
     while true 
        while (a[i] < v)
           i = i + 1
        while (a[j] > v)
           j = j - 1
        if (j == l)
           break
        if (i [math] \geqslant [/math] j) 
           break
        swap(a[i], a[j])
     swap(a[i], a[r])
     return i

Асимптотика

Худшее время работы

Предположим, что мы разбиваем массив так, что одна часть содержит [math]n - 1[/math] элементов, а вторая — [math]1[/math]. Поскольку процедура разбиения занимает время [math]\Theta(n)[/math], для времени работы [math]T(n)[/math] получаем соотношение:


[math]T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)[/math].

Мы видим, что при максимально несбалансированном разбиении время работы составляет [math]\Theta(n^2)[/math]. В частности, это происходит, если массив изначально отсортирован.

Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного

В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает [math]\Theta(n^2)[/math] сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться [math]1[/math], а в другом [math] n - 1 [/math] элемент).

Заполним сначала массив [math]a[/math] длины [math]n[/math] элементами от [math]1[/math] до [math] n [/math], затем применим следующий алгоритм (нумерация с нуля): 

  void antiQsort(a: int[n])
     for i = 0 to n - 1 
        swap(a[i], a[i / 2])

Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.

При выполнении [math]\mathrm{partition}[/math] делается [math]\Theta(n)[/math] сравнений из-за того, что с помощью индексов [math]i[/math] и [math]j[/math] мы проходим в лучшем случае [math]\Omega(n)[/math] элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае [math]O(2n)[/math] элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура [math]\mathrm{partition}[/math] делает [math]\Theta(n)[/math] сравнений с точностью до константы.

Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. [math]\mathrm{antiQsort}[/math] на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А [math]\mathrm{partition}[/math] делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как [math] \mathrm{antiQsort} [/math] на массиве любой длины будет выполнять операции, обратные [math]\mathrm{partition}[/math]. Фактически, [math]\mathrm{partition}[/math] — это [math]\mathrm{antiQsort}[/math], запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала [math]i[/math] дойдет до середины массива, до опорного элемента, [math]j[/math] останется равным индексу последнего элемента. Затем произойдет [math]\mathrm{swap}[/math] и [math]i[/math] снова начнет увеличиваться, пока не дойдет до последнего элемента, [math]j[/math] опять не изменит свою позицию. Потом произойдет выход из [math]\mathrm{while}[/math].

Разбиение массива будет произведено [math]\Theta(n)[/math] раз, потому что разбиение производится на массивы длины [math]1[/math] и [math] n - 1 [/math] из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется [math]\Theta(n)[/math] [math]\mathrm{partition}[/math] и [math]\Theta(n)[/math] сравнений для каждого выполнения [math]\mathrm{partition}[/math]. Тогда быстрая сортировка выполнит [math]\Theta(n^2)[/math] сравнений для массива, построенного таким способом.

Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае — [math]\Theta(n^2)[/math]) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной [math]1[/math] и [math]n-1[/math] на каждой итерации. Создадим массив [math]a[/math] длины [math]n[/math], заполненный элементами типа [math]pair[/math]. Такой элемент хранит пару значений [math](val, key)[/math], где [math]val[/math] — элемент массива, а [math]key[/math] — индекс. Изначально [math]a[i][/math] элемент имеет вид [math](0, i)[/math].

Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа [math]pair[/math] по их значениям [math]val[/math]. На каждом шаге будем выполнять следующие действия: при обращении к [math]i[/math]-ому элементу в качестве опорного на шаге под номером [math]k[/math], присвоим [math]val = n-k+1[/math] для элемента [math]a[i][/math]. Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы [math]pair[/math] по значениям [math]key[/math]. Искомым будет являться массив элементов [math]val[/math] в соответствующей последовательности.

Пример для [math]n = 4[/math], при последовательном выборе опорных элементов [math]2, 2, 1, 1[/math].


Построение массива
Шаг 1.0 Шаг 1.1 Шаг 1.2 Шаг 2.0 Шаг 2.1 Шаг 2.2 Шаг 3.0
1 2 3 4 <br\> 0 0 0 0 1 2 3 4 <br\> 0 4 0 0 1 4 3 2 <br\> 0 0 0 4 1 4 3 2 <br\> 0 0 0 4 1 4 3 2 <br\> 0 3 0 4 1 3 4 2 <br\> 0 0 3 4 1 3 4 2 <br\> 0 0 3 4
Шаг 3.1 Шаг 3.2 Шаг 4.0 Шаг 4.1 Шаг 4.2 Результат
1 3 4 2 <br\> 2 0 3 4 3 1 4 2 <br\> 0 2 3 4 3 1 4 2 <br\> 0 2 3 4 3 1 4 2 <br\> 1 2 3 4 3 1 4 2 <br\> 1 2 3 4 1 2 3 4 <br\> 2 4 1 3
Итоговый массив

2 4 1 3

Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении [math]\mathrm{quicksort}[/math] алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части — большие или равные опорному элементы и меньшие его — на каждом шаге имеем разбиение на массивы длины [math]1[/math] и [math]n-1[/math], чего мы, собственно, и добивались. При таком выполнении алгоритма происходит [math]\Theta(n^2)[/math] разделений на два подмассива, и на каждом разделении выполняется [math]\Theta(n^2)[/math] сравнений. Следовательно, на данном массиве быстрая сортировка работает за [math]\Theta(n^2)[/math].

Среднее время работы

Лемма:
Время работы алгоритма быстрой сортировки равно [math]O(n \log n)[/math].
Доказательство:
[math]\triangleright[/math]

Пусть Х — полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как [math]z_1 \ldots z_n[/math], где [math]z_i[/math] наименьший по порядку элемент. Также введем множество [math]Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}[/math].

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

Поскольку каждая пара элементов сравнивается не более одного раза, полное количество сравнений выражается как

[math]X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}[/math], где [math]X_{ij} = 1[/math] если произошло сравнение [math]z_i[/math] и [math]z_j[/math] и [math]X_{ij} = 0[/math], если сравнения не произошло.

Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим

[math]E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i[/math] сравнивается с [math]z_j\}[/math]

Осталось вычислить величину [math]Pr\{z_i[/math] сравнивается с [math]z_j\}[/math] — вероятность того, что [math]z_i[/math] сравнивается с [math]z_j[/math]. Поскольку предполагается, что все элементы в массиве различны, то при выборе [math]x[/math] в качестве опорного элемента впоследствии не будут сравниваться никакие [math]z_i[/math] и [math]z_j[/math] для которых [math]z_i \lt x \lt z_j[/math]. С другой стороны, если [math]z_i[/math] выбран в качестве опорного, то он будет сравниваться с каждым элементом [math]Z_{ij}[/math] кроме себя самого. Таким образом элементы [math]z_i[/math] и [math]z_j[/math] сравниваются тогда и только тогда когда первым в множестве [math]Z_{ij}[/math] опорным элементом был выбран один из них.

[math]Pr\{z_i[/math] сравнивается с [math]z_j\} = Pr\{[/math]первым опорным элементом был [math]z_i[/math] или [math]z_j\} = Pr\{[/math]первым опорным элементом был [math]z_i\} + Pr\{[/math]первым опорным элементом был [math]z_j\} = [/math] [math] =\dfrac {1}{j-i+1} + \dfrac {1}{j-i+1} = \dfrac {2}{j-i+1} [/math]

[math] E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \dfrac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k+1} \lt \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k} [/math] [math]= \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n) [/math]
[math]\triangleleft[/math]

Mатожидание времени работы быстрой сортировки будет [math]O(n \log n)[/math].

Модификации

Нерекурсивная реализация быстрой сортировки

Для выполнения быстрой сортировки можно воспользоваться стеком, в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек. Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке [math]N[/math] элементов не превосходила величины [math]\log n[/math]. 

  void quicksort(a: int[n], int l, int r)
     stack< pair<int,int> > s   
     s.push(l, r);
     while (!s.empty())
        l = s.pop()
        r = s.pop()
        if (r [math] \leqslant [/math] l)
           continue
        int i = partition(a, l, r);
        if (i - 1 > r - i) 
           s.push(l, i - 1)
           s.push(i + 1, r)
        else
           s.push(i + 1, r)
           s.push(l, i - 1)

Улучшенная быстрая сортировка

Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может привести к существенному повышению эффективности быстрой сортировки. Данная реализация осуществляет разделение по медиане из первого, среднего и последнего элементов массива. Массивы небольшого размера (длиной [math]M = 11[/math] и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется сортировка вставками. 

  const int M = 10
  void quicksort(a: int[n], int l, int r)
     if (r - 1 [math] \leqslant [/math] M)
        return
     swap(a[(l + r)/2], a[r - 1])
     median(a[l], a[r - 1], a[r])
     int i = partition(l + 1, r - 1)
     quicksort(a, l, i - 1)
     quicksort(a, i + 1, r)

  void hybridsort(a: int[n], int l, int r)
     quicksort(a, l, r)
     insertion(a, l, r)

Быстрая сортировка с разделением на три части

Когда в сортируемом массиве имеется множество повторяющихся ключей предыдущие реализации быстрой сортировки можно существенно улучшить. Например массив, который состоит из равных ключей, вовсе не нуждается в дальнейшей сортировке, однако предыдущие реализации продолжают процесс разделения, подвергая обработке все более мелкие подмассивы, независимо от того, насколько большим является исходный файл.

G3.png

В основу программы положено разделение массива на три части: на элементы,меньшие разделяющего элемента [math] a[l] \ldots a[j][/math], элементы, равные разделяющему элементу [math]a[j+1] \ldots a[i-1][/math], и элементы большие разделяющего элемента [math]a[i] \ldots a[r][/math]. После этого сортировка завершается двумя рекурсивными вызовами.

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

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

  void quicksort(a: int[n], int l, int r)
     int k
     int v = a[r]
     if (r [math] \leqslant [/math] l)
        return
     int i = l
     int j = r - 1
     int p = l - 1
     int q = r
     while true 
        while (a[i] < v)
           i++
        while (a[j] > v)
           j--
        if (i == j)
           break
        if (i [math] \geqslant [/math] j)
           break
        swap(a[i], a[j])
        if (a[i] == v)
           p++
           swap(a[p], a[i])
        if (a[j] == v)
           q--
           swap(a[q], a[j])
     swap(a[i], a[r])
     j = i - 1
     i++
     for (k = 1 ; k [math] \leqslant [/math] p; k++, j--) 
        swap(a[k],a[j])
     for (k = r-1; k [math] \geqslant [/math] q; k--, i++) 
        swap(a[k],a[i]) 
     quicksort(a, 1, j) 
     quicksort(a, i, r)

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка&oldid=55181»