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

Сегодня рассказывала на лекции про сортировки.
    Вставкой
    Пузырьком
    Шейкер
    Выбором
    Подсчетом
    Хоара — быстрая

Все кроме последней элементарно объясняются в википедии и в интернете вообще, а последняя через попу. Ща попытаюсь объяснить понятно. Скажете, что неясно.

Краткое описание

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

Еще раз: после первого прохода список разделяется на две части. Затем, берется первая, и для нее вызывается та же сортировка, в результате которой этот подсписок (первая часть) тоже разбивается на 2, и т. д., пока в принимаемом списке не останется один элемент. То же повторяется и для второй части. Следовательно, удобно использовать рекурсию для написании этой сортировки.

Подробное описание. Пример

Для того, чтобы разбить список на 2 части относительного некоторого элемента, нужно выбрать этот элемент. Можно выбирать случайно, то есть любой. Я рассмотрю случай, когда элемент выбирается как серединный: (левая граница списка + правая граница) разделить на 2 = (l + r) / 2 = (0 + 7) / 2 = 3.

22    7    10    0    6    6   1
 0     1     2     3    4    5   6

 l                                         r

Серединный — a[3] = 0.

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

0    7    10    22    6    6   1

Далее находим границы списка, который мы будем анализировать. Левая граница (назовем ее l) будет находиться на первой позиции (если считать с нуля), так как на нулевой лежит избранный элемент. А правая (назовем ее r) будет находиться на конце списка и будет равна его размерности. Итак, диапазон анализируемых значений будет [l ; r), не включая правую границу.

0    7    10    22    6    6   1

      l                                     r

Давайте анализировать. Элемент а[l] > 0, значит, меняем его с a[r - 1]. И так как справа у нас находятся большие элементы, то правая граница анализируемой части подвигается влево на один.

0    1    10    22    6    6   7

      l                                r

Далее, a[l] > 0, обмениваем его с a[r - 1]. Сдвигаем правую границу.

0    6    10    22    6    1   7

      l                           r

И так далее, пока r и l не станут равными: r = l.

0    6    10    22    6    1   7

      l                      r

0    22    10    6    6    1   7

       l               r

0    10    22    6    6    1   7

       l       r

0    10    22    6    6    1   7

      l r

Далее необходимо базовый элемент положить как раз на границу двух списков: чтобы справа от него были те, что меньше него, а слева — те, что больше него. Очевидно эта граница находится на позиции l - 1.

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

10   22    6    6    1   7

Выбираем базовый элемент — a[3]. Срединный — «6», меняем его с нулевым.

10   22    6    6    1   7

6    22     6   10   1   7

Расставляем границы.

6    22    6   10   1   7

       l                           r

Сравниваем поочередно элементы a[l] с базовым «6». a[l] > 6, поэтому

6    7     6    10   1   22

      l                         r

a[l] снова больше чем 6.

6    1    6    10    7   22

      l                   r

А вот сейчас a[l] < 6, поэтому мы не производим обмен, а сдвигаем левую границу вправо на один элемент.

6    1     6    10    7   22

             l             r

6 <= 6, левая граница подвигается

6    1    6     10    7   22

                    lr

Сейчас r = l, вставляем базовый элемент в l - 1

6    1    6    10    7   22

                   lr     

Получилось, что мы разбили подсписок на 2 части (с нулевого по l-ый — третий и с l-ого по r-ый — с третьего по пятый, не включая правые границы, как всегда):

     6    1    и    10    7   22
№ 0    1           2     3    4 

Рассмотрим первую часть:

6    1

Выберем базовый элемент (0 + 2)/2 = 1, переместим на место первого, ставим границы

1    6  

      l   r

Проводим те же операции, в результате получим

1    6 

      lr

и разделим  на два подсписка: пустой и «6», которые уже отсортированы.

Далее, обработаем вторую часть исходного списка:

10    7   22

7    10   22

        l           r

7   22   10

      l      r

7   10   22

      lr

Делим на два списка:

пустой и «10   22»

Обработаем второй (0 + 2) / 2 = 1:

10    22

22    10

         l     r

22    10

              lr

Возвращаем базовый элемент на нужное место (l - 1):

10    22

              lr

Разбиваем на два списка: «10» и пустой, которые уже отсортированы. Соединим все полученные подсписки в один

0    1     6     6    7    10    22.

Сложность

Сложность данного алгоритма в худшем случае (когда после разделения на элементы, большие базового и меньшие базового, получается два списка: пустой и из оставшихся элементов) O(n^2), что не отличает данную сортировку от всех вышеперечисленных «небыстрых». Но в среднем случае, когда базовый элемент разбивает при каждом проходе список примерно на два подсписка равной длины, мы получаем сложность n * log_2(n). Почему:

За один проход мы перебираем n элементов — n операций. Но каждый следующий проход делит список на два (при этом количество перебираемых (сравниваемых) элементов не уменьшается, так как мы сортируем обе половины), в итоге количество проходов равно двоичному логарифму от n — log_2(n).


Для тех, кто не помнит, что такое логарифм: сколько раз нужно умножить 2 само на себя, чтобы получилось n? log_2(n). То есть количество делений нашего списка на два, пока не останется список из одного (или нуля) элементов.