Лекция 3.

Сегодня вашим лектором впервые буду я, Слава Муравьев)  Мою лекцию я разделю на 2 части:
А) Обоснование корректности и асимптотики квиксорта (быстрой сортировки) на пальцах
Б) Рассказ еще об одной сортировке, обладающей асимптотикой O(N * log(N))

Часть А.

Здесь могли бы быть строгие математические доказательства с кучей формул, но вряд ли они вам когда-нибудь пригодятся)
Быстрая сортировка работает по принципу "разделяй и властвуй" - довольно известный подход к решению многих задач.

Алгоритм квиксорта состоит из двух основных частей:
1) Выбирается "опорный" элемент, и массив разбивается по следующему правилу:
Все элементы, меньше или равные опорному элементу, должны иметь меньший индекс, чем опорный, а больше - больший индекс.
Заметим, что мы не требуем упорядоченности элементов слева и справа от опорного, мы лишь задаем для них верхнюю/нижнюю границу.
2) Алгоритм быстрой сортировки запускается для части массива, меньшей опорного, затем - для большей.

Соответственно, выход из рекурсии мы осуществим, когда сортировать будет нечего - мы доберемся до пустого массива.

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

Теперь асимптотика. Каждое разбиение массива мы будем производить за O(N) - будем пробегать массив двумя указателями,
один будет искать элемент, больший опорного с индексом, меньшим индекса опорного, второй - меньший опорного с большим индексом.
Когда оба указателя найдут такие элементы, нам остается только переставить местами эти элементы и продолжить двигать указатели до их пересечения.
В этом случае каждый указатель сделает максимум N перемещений (мы же по массиву его двигаем, к тому же только в одну сторону).

Но у нас остается вопрос - а сколько раз мы будем делать такие разбиения массива? Если посмотреть на наш алгоритм, то можно заметить, что в среднем
он всегда делит массив на 2 примерно равные части, то есть длина сортируемого массива уменьшается примерно вдвое при каждом заходе в рекурсию.
Максимум таких делений будет log_2(N), а на каждом уровне мы будем делать разбиения нескольких массивов, в сумме пробегая все равно целый массив длины N.
Отсюда мы сделаем O(N * log(N)) операций, что и требовалось показать.