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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (minor)
м (minor)
Строка 44: Строка 44:
 
Заполним сначала массив <tex>A</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):
 
Заполним сначала массив <tex>A</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):
 
   
 
   
   '''function''' antiQsort (A: '''int'''[n]):
+
   '''function''' antiQsort(A: '''int'''[n]):
 
       '''for''' i = 0 '''to''' n - 1  
 
       '''for''' i = 0 '''to''' n - 1  
 
         swap(A[i], A[i / 2])
 
         swap(A[i], A[i / 2])
Строка 51: Строка 51:
 
При выполнении <tex>\mathrm{partition}</tex> делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</tex> делает <tex>\Theta(n)</tex> сравнений с точностью до константы.
 
При выполнении <tex>\mathrm{partition}</tex> делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</tex> делает <tex>\Theta(n)</tex> сравнений с точностью до константы.
  
Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. <tex>\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{---}} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону.
+
Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. <tex>\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{---}} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала <tex>i</tex> дойдет до середины массива, до опорного элемента, <tex>j</tex> останется равным индексу последнего элемента. Затем произойдет <tex>\mathrm{swap}</tex> и <tex>i</tex> снова начнет увеличиваться, пока не дойдет до последнего элемента, <tex>j</tex> опять не изменит свою позицию. Потом произойдет выход из <tex>\mathrm{while}</tex>.
  
 
Разбиение массива будет произведено <tex>\Theta(n)</tex> раз, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше).  Следовательно, на массиве, который строится описанным выше способом, выполняется <tex>\Theta(n)</tex> <tex>\mathrm{partition}</tex> и <tex>\Theta(n)</tex> сравнений для каждого выполнения <tex>\mathrm{partition}</tex>. Тогда быстрая сортировка выполнит <tex>\Theta(n^2)</tex> сравнений для массива, построенного таким способом.
 
Разбиение массива будет произведено <tex>\Theta(n)</tex> раз, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше).  Следовательно, на массиве, который строится описанным выше способом, выполняется <tex>\Theta(n)</tex> <tex>\mathrm{partition}</tex> и <tex>\Theta(n)</tex> сравнений для каждого выполнения <tex>\mathrm{partition}</tex>. Тогда быстрая сортировка выполнит <tex>\Theta(n^2)</tex> сравнений для массива, построенного таким способом.

Версия 15:20, 8 января 2016

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

Алгоритм

  • из массива выбирается некоторый опорный элемент [math]A[i][/math].
  • запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные [math]A[i][/math], влево от него, а все ключи, большие, либо равные [math]A[i][/math] — вправо.
  • для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

Псевдокод

  function 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[p..r][/math] нужным образом:

  int partition(A: int[n], int l, int r):
      x = A[l]
      i = l
      j = r
      while true 
          while A[i] < x 
               i = i + 1
          while A[j] > x 
               j = j - 1
          if i < j 
              swap(A[i++], A[j--])
          else 
              return j

Асимптотика

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

Предположим, что мы разбиваем массив так, что одна часть содержит [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], затем применим следующий алгоритм (нумерация с нуля):

  function 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]O(n \log n)[/math].
Доказательство:
[math]\triangleright[/math]

Пусть Х — полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как [math]z_1...z_n[/math], где [math]z_i[/math] наименьший по порядку элемент. Также введем множество [math]Z_{ij} = \{z_i, z_{i+1}...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\} = \frac {1}{j-i+1} + \frac {1}{j-i+1} = \frac {2}{j-i+1} [/math]

[math] E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} \lt \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \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]O(n)[/math], а время работы алгоритма [math]O(n^2)[/math]. Существуют различные способы разбиения массива, направленные против худшего случая:

  • При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — [math]O(n \log n)[/math].
  • Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов).
  • Разбивать массив не на две, а на три части.

Оптимизация глубины рекурсии до O(logn) в худшем случае

Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит [math]\log n[/math], а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

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