Быстрая сортировка и разбиение Хоара

Если ты умеешь разбивать массив вокруг опорного двумя встречными указателями (Хоар) и знаешь, почему быстрая сортировка в среднем Θ(n·log n) и работает на месте, листай до «Теперь сам».

Как думаешь, можно ли сортировать делением пополам, но без лишней памяти

Сортировка слиянием делит массив по СЕРЕДИНЕ (пополам по позиции) и всю работу переносит в дорогое слияние, которому нужна память. А что, если делить не по позиции, а по ЗНАЧЕНИЮ: выбрать какое-то число - опорное - и раскидать массив так, чтобы слева от него оказались все меньшие, справа все большие? Тогда опорный сразу на своём финальном месте, а сливать НИЧЕГО не надо - обе части уже стоят по местам, их только досортировать. Вся работа уходит в разбиение, и его можно сделать НА МЕСТЕ. Это и есть быстрая сортировка.

На что это похоже

Ты сортируешь класс по росту. Выбираешь одного ученика (опорного) и командуешь: кто ниже - встань слева от него, кто выше - справа. Теперь этот ученик точно на своём месте, а задача распалась на две поменьше: упорядочить левую группу и правую тем же приёмом. Ты не переписываешь весь класс в новый список - ты переставляешь людей ПРЯМО в шеренге. Никакой лишней «второй шеренги», как при слиянии, не нужно.

Механизм: разбиение Хоара двумя встречными указателями

Выберем опорным первый элемент, p = a[low], и пока оставим его на месте (в ячейке low). Левый указатель i пойдёт от элемента СРАЗУ ЗА опорным (low+1) вправо, правый j - от конца влево, навстречу. Дальше повторяем:

• двигаем i вправо, пока a[i] < p (ищем элемент, который «не на своей стороне» - большой, застрявший слева, то есть первый ≥ p);
• двигаем j влево, пока a[j] > p (ищем маленький, застрявший справа, - первый ≤ p);
• если i ещё левее j - меняем a[i] и a[j] местами (каждый переезжает на свою сторону) и продолжаем;
• как только указатели встретились или пересеклись - ставим опорный на его место: меняем a[low] с a[j] (там j показывает на последний элемент, не больший опорного).

Теперь опорный на позиции j: слева от него всё ≤ p, справа всё ≥ p. Рекурсивно сортируем часть [low..j−1] и часть [j+1..high] (сам опорный уже на месте).

Правило

Быстрая сортировка выбирает опорный, разбивает массив на «меньше» и «больше» него (опорный встаёт на финальное место) и рекурсивно сортирует обе части. Разбиение Хоара - два указателя навстречу: левый ищет элемент ≥ опорного, правый ≤ опорного, найденную пару меняют, пока указатели не встретятся. В среднем Θ(n·log n), работает НА МЕСТЕ. Разбиение стоит Θ(n) за проход, а рекурсия по половинам даёт логарифм уровней - как у слияния, но без буфера.

Разбор: почему в среднем Θ(n·log n)

Одно разбиение проходит массив указателями навстречу - Θ(n). Если опорный делит массив примерно ПОПОЛАМ, получается та же рекуррентность, что у слияния: T(n) = 2T(n/2) + n = Θ(n·log n). «Примерно пополам» не обязано быть точным: даже если опорный всякий раз отрезает, скажем, четверть и три четверти, число уровней остаётся Θ(log n) (глубина дерева при делении в постоянной пропорции логарифмическая), и выходит тот же Θ(n·log n). На случайных данных опорный в среднем делит достаточно сбалансированно, поэтому средний случай - Θ(n·log n). Разница со слиянием - в том, что здесь n·log n НЕ гарантирован: если опорный раз за разом отрезает по одному элементу, дерево вырождается в цепочку - об этом худшем случае следующий урок.

Разбор: почему на месте и почему не устойчива

Быстрая сортировка не создаёт новых массивов: разбиение переставляет элементы прямо внутри исходного, меняя пары местами. Поэтому ей нужна лишь Θ(log n) памяти под стек рекурсии (глубину вызовов), а не Θ(n) буфер, как слиянию, - это её большое практическое преимущество. Плата за перестановки на месте - потеря устойчивости: обмен далёких элементов при разбиении легко перепрыгивает равные друг через друга, и их исходный порядок не сохраняется. Поэтому, когда важна устойчивость (сортировка по второму ключу), берут слияние, а не быструю. Быстрая - это «память и скорость на практике» против «гарантия и устойчивость» у слияния.

Что ломается без этого

Первая ошибка в разбиении Хоара - неверно двигать указатели или перепутать строгие и нестрогие сравнения, из-за чего указатели «проскакивают» друг друга или зацикливаются на равных опорному элементах: разбиение либо не завершается, либо теряет элемент. Классика - забыть в конце поставить опорный на место (поменять a[low] с a[j]): тогда он так и останется слева, и разбиение будет неверным. Поставив опорный на позицию j, рекурсию ведут по [low..j−1] и [j+1..high], ИСКЛЮЧАЯ сам j (он уже на месте). Вторая - выбрать опорный «в лоб» (всегда первый) и нарваться на худший случай на уже отсортированных данных. Третья - ждать от быстрой сортировки устойчивости: её нет.

Зачем это в работе

Быстрая сортировка - самая используемая сортировка для примитивов (чисел) в стандартных библиотеках: в C её qsort, в Java Arrays.sort для примитивных типов - варианты быстрой (обычно с защитой от худшего случая, см. следующий урок). Причина - она сортирует НА МЕСТЕ (не ест лишнюю память) и на реальных данных с хорошими константами обгоняет слияние. Разбиение (partition) - ещё и самостоятельный полезный приём: тот же шаг «расставить относительно опорного» лежит в основе быстрого ВЫБОРА k-го элемента (quickselect) без полной сортировки - об этом в разделе про порядковые статистики. Понимать разбиение Хоара - значит понимать сердце и быстрой сортировки, и быстрого выбора.

Теперь сам

Опорный p = 5, массив [5, 2, 8, 1, 9, 3]. Проведи одно разбиение Хоара по шагам: что найдут указатели и какие пары поменяются? К чему в итоге придёт массив (примерно)?