Разделение списка
на две группы

Категория

Алгоритм

Уровень

Средний

Опирается на

Главы 8.4 и 8.7

Зачем это знать

Разделение — основной шаг быстрой сортировки

§1Что такое разделение

Разделение отличается от сортировки: внутри групп порядок не определён. Поэтому оно дешевле — O(n) за один проход, тогда как сортировка стоит O(n log n). Способ зависит от одного вопроса к условию: нужно ли сохранить порядок элементов внутри групп.

§2Перенос нулей: указатели в одну сторону

Схема та же, что в главе 8.7: r читает каждое число, w показывает место для следующего ненулевого. Отличие в одном: вместо записи nums[w] = nums[r] выполняется обмен nums[w], nums[r] = nums[r], nums[w]. Ноль, который стоял в позиции w, при этом переезжает на место r. Поэтому после цикла обрезать хвост не нужно: в нём и так стоят нули, и длина списка не меняется.

1. Прочитать. Взять nums[r].
2. Не ноль. Поменять местами nums[w] и nums[r] и сдвинуть w: число встало в конец группы ненулевых.
3. Ноль. Ничего не делать, w остаётся на месте.
4. Следующий. Сдвинуть r и повторить до конца списка. Возвращать ничего не нужно: список изменён на месте.

Пройдите алгоритм сами: на каждом шаге решите, переносить прочитанное число вперёд или пропустить.

§3Сборка move_zeros из строк

Функция короткая — шесть строк, но в ней легко перепутать уровни отступа: w += 1 выполняется только для ненулевого числа, внутри if. Расставьте строки, затем напишите функцию сами.

>>> nums = [0, 4]
>>> nums[0], nums[1] = nums[1], nums[0]
>>> nums
[4, 0]

Напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на четырёх входах, как в песочнице главы 8.4; часть из них заготовка проходит сразу.

§4Код и прогон переноса нулей

def move_zeros(nums):
    w = 0
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

Инвариант: перед шагом r в nums[0:w] стоят все ненулевые числа из прочитанной части в исходном порядке, а в nums[w:r] — только нули. Обмен сохраняет его: ненулевое число встаёт в конец первой зоны, ноль из позиции w уходит в конец второй. Порядок ненулевых не меняется, потому что каждое следующее встаёт правее предыдущего.

§5Разделение по порогу: указатели навстречу

Второй способ подходит, когда порядок внутри групп не важен. Задача: переставить числа так, чтобы все числа меньше порога limit стояли в начале, и вернуть их количество. Указатели стартуют с двух концов. i идёт вправо, пока число под ним уже на своей стороне — меньше порога. j идёт влево, пока число под ним не меньше порога. Когда оба остановились, числа под ними стоят не на своих сторонах, и их меняют местами.

1. Левый на месте. Если nums[i] меньше порога, оно уже в своей группе: сдвинуть i вправо.
2. Правый на месте. Иначе, если nums[j] не меньше порога, оно тоже на месте: сдвинуть j влево.
3. Оба не на месте. Иначе слева стоит большое число, а справа маленькое: поменять их местами и сдвинуть оба указателя.
4. Конец. Повторять, пока i <= j. После цикла i — число элементов меньше порога.

def split_by_limit(nums, limit):
    i, j = 0, len(nums) - 1
    while i <= j:
        if nums[i] < limit:
            i += 1
        elif nums[j] >= limit:
            j -= 1
        else:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    return i

>>> x = 5
>>> if x < 0:
...     print("меньше нуля")
... elif x == 0:
...     print("ноль")
... else:
...     print("больше нуля")
...
больше нуля

Прогон ниже — на списке [5, 12, 3, 18, 7, 25, 1] с порогом 10. Зелёные ячейки — числа, которые уже стоят на своих сторонах: слева от i — меньше 10, справа от j — не меньше.

Инвариант: всё левее i меньше порога, всё правее j — не меньше. После цикла i = j + 1, и граница между группами проходит по индексу i. В примере функция вернула 4: числа 5, 1, 3, 7 меньше 10.

Условие цикла здесь i <= j, а в задаче 1 было i < j. В задаче 1 один оставшийся элемент пары не образует, и проверять его незачем. При разделении каждый элемент нужно отнести к одной из групп, в том числе тот, на котором сошлись указатели. Если его не проверить, возвращённое i может оказаться на единицу меньше. Обе версии запущены на [8, 0, 12, 9, 5, 3] с порогом 10: чисел меньше 10 здесь пять.

§6Сравнение двух способов

Посмотрим на результат второго способа внимательнее. Исходный список [5, 12, 3, 18, 7, 25, 1], результат [5, 1, 3, 7, 18, 25, 12]. Числа 12, 18, 25 шли в исходном списке в этом порядке, а в результате стоят как 18, 25, 12: порядок внутри группы не сохранился. Для разделения это допустимо, для переноса нулей по условию — нет.

В карточке изменения занятия 7 была задача split_spam: сначала обычные комментарии в исходном порядке, потом спам в любом порядке. Это разделение с сохранением порядка первой группы — то есть первый способ.

§7Три группы за один проход

Задача LeetCode 75 Sort Colors просит разложить список из чисел 0, 1 и 2 по возрастанию за один проход. Её решают тремя указателями: low — граница нулей, high — граница двоек, mid читает. Нули обмениваются к low, двойки — к high, единицы остаются посередине. Это сочетание обеих форм: low и mid идут в одну сторону, mid и high — навстречу. Ниже код, пошаговый прогон на списке [2, 0, 2, 1, 1, 0] и проверка запуском. Зелёные ячейки в прогоне — готовые группы: нули левее low и двойки правее high.

1. Ноль. Если nums[mid] — ноль, обменять его с nums[low] и сдвинуть и low, и mid.
2. Единица. Если единица, она уже посередине: сдвинуть только mid.
3. Двойка. Если двойка, обменять её с nums[high] и сдвинуть high влево. mid не двигается: пришедшее число ещё не проверено.
4. Конец. Повторять, пока mid <= high.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

>>> nums = [2, 0, 2, 1, 1, 0]
>>> sort_colors(nums)
>>> nums
[0, 0, 1, 1, 2, 2]

После обмена с low указатель mid сдвигается: из позиции low пришло уже прочитанное число, ноль или единица. После обмена с high указатель mid остаётся на месте: на его место пришло число из непрочитанной части, и его ещё нужно проверить. Если сдвигать mid и здесь, пришедшее число пропускается. На списке из прогона выше это незаметно, поэтому обе версии запущены на [1, 2, 0].

§8Проверьте себя