Сегодня рассказывала на лекции про сортировки.
Вставкой
Пузырьком
Шейкер
Выбором
Подсчетом
Хоара — быстрая
Все кроме последней элементарно объясняются в википедии и в интернете вообще, а последняя через попу. Ща попытаюсь объяснить понятно. Скажете, что неясно.
Краткое описание
Суть этой сортировки заключается в том, что после каждого прохода все элементы разделяются на две группы: слева находятся меньшие, чем какой-либо элемент, а справа — большие. После каждого прохода берется каждая из двух частей и сортируется тем же способом, то есть задача сводится к предыдущей. Так происходит пока все подчасти не будут состоять из одного элемента. Таким образом, количество элементов в сортируемой части уменьшается при каждом следующем вызове функции из себя же.
Еще раз: после первого прохода список разделяется на две части. Затем, берется первая, и для нее вызывается та же сортировка, в результате которой этот подсписок (первая часть) тоже разбивается на 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]. И так как справа у нас находятся большие элементы, то правая граница анализируемой части подвигается влево на один.
Далее, a[l] > 0, обмениваем его с a[r - 1]. Сдвигаем правую границу.
И так далее, пока r и l не станут равными: r = l.
Далее необходимо базовый элемент положить как раз на границу двух списков: чтобы справа от него были те, что меньше него, а слева — те, что больше него. Очевидно эта граница находится на позиции 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, поэтому
a[l] снова больше чем 6.
А вот сейчас a[l] < 6, поэтому мы не производим обмен, а сдвигаем левую границу вправо на один элемент.
6 <= 6, левая граница подвигается
Сейчас r = l, вставляем базовый элемент в l - 1
Получилось, что мы разбили подсписок на 2 части (с нулевого по l-ый — третий и с l-ого по r-ый — с третьего по пятый, не включая правые границы, как всегда):
6 1 и 10 7 22
№ 0 1 2 3 4
Рассмотрим первую часть:
6 1
Выберем базовый элемент (0 + 2)/2 = 1, переместим на место первого, ставим границы
1 6
l r
Проводим те же операции, в результате получим
и разделим на два подсписка: пустой и «6», которые уже отсортированы.
Далее, обработаем вторую часть исходного списка:
10 7 22
7 10 22
l r
Делим на два списка:
пустой и «10 22»
Обработаем второй (0 + 2) / 2 = 1:
10 22
22 10
l r
Возвращаем базовый элемент на нужное место (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). То есть количество делений нашего списка на два, пока не останется список из одного (или нуля) элементов.
