Информатика · объяснение и практика

Разбиение около опорного: что гарантирует один шаг быстрой сортировки

Что делает разбиение около опорного элемента: области меньше, равно и больше, их инварианты и границы обещания одного шага.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Поиск и сортировка · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

Разбиение распределяет элементы относительно выбранной опоры. После корректного шага меньшие значения находятся с одной стороны, большие — с другой; внутри этих областей порядок может оставаться произвольным. Это ещё не полная сортировка списка.

Отделяем отношение к опоре от общего порядка

Выберем опорное значение и для каждого элемента зададим только один вопрос: меньше он, равен или больше. Такое распределение создаёт крупные области, но ничего не говорит о взаимном порядке двух чисел внутри одной области. Например, оба числа восемь и шесть больше пяти, даже если восьмёрка стоит раньше шестёрки.

Существуют разные схемы partition. Одни возвращают окончательную позицию конкретного опорного элемента, другие — только границу двух частей. В учебном трёхчастном представлении удобно явно выделить область равных значений. Свойства одной схемы нельзя автоматически переносить на другую только потому, что обе называются разбиением.

Проверяем результат относительно выбранного значения

Пусть исходные числа — 9, 2, 5, 1, 5, 7, а опора равна пяти. Возможный результат распределения: 2, 1 | 5, 5 | 9, 7. Слева стоят только меньшие, в середине — равные, справа — только большие. Сами пары 2,1 и 9,7 всё ещё убывают.

Поэтому проверка «после partition весь массив отсортирован» неверна. Нужны отдельные проверки границ областей, отношения каждого элемента к опоре и сохранения всех исходных элементов вместе с повторениями. Для последнего условия мало сравнить множества: множество забывает, сколько раз встречалось одинаковое значение.

Пример

Опора 5: [9,2,5,1,5,7] → [2,1] | [5,5] | [9,7].

Разбиение верно, полная сортировка ещё не завершена. Две пятёрки должны сохраниться обе; число различных значений не заменяет подсчёт элементов.

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

Быстрая сортировка продолжает упорядочивать области меньших и больших значений. В трёхчастном варианте равная область уже не нуждается в перестановках по тому же ключу. Если данных с повторениями много, явное выделение равных помогает избежать бесполезной повторной обработки одинаковых значений.

Для реализации с перестановками на месте важно продвигать границы и гарантировать уменьшение ещё не обработанной области. Иначе равные опоре значения способны привести к зацикливанию ошибочного кода. Перед разбором скорости сначала сформулируйте постусловие конкретной схемы и проверьте его на списке из одних одинаковых чисел.

От чтения к действию

А теперь — вы

После разбиения вокруг 4 получено [3,1] | [4,4] | [8,6]. Как оценить результат?

Частые вопросы

У всех partition опора сразу стоит на окончательном месте?

Нет. Это зависит от схемы; некоторые варианты возвращают лишь границу разделения.

Нужно сортировать область равных ещё раз?

В трёхчастной схеме по тому же ключу не нужно: все её значения равны.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться