Не удается ли разделение Hoare в некоторых случаях?

Question

Работал над проблемой разбиения Hoare и понял, что разделение Hoare, похоже, не в состоянии правильно сортировать элементы в случае, когда левый и правый указатели одновременно сталкиваются со значением, равным центральной точке.

Например, для массива [0,2,1,0,2,1,2,0], если вы выбрали 1 в качестве точки поворота, левый и правый указатели встретятся с двумя единицами в одно и то же время, поменяйте местами их, а затем продолжите, выдав неправильный вывод [0,0,1,0,2,1,2,2]

Известно ли, что это проблема с разделением Hoare? Как люди обычно имеют дело с этим делом?

Для справки, это код, который я использую:

def hoarePartition(nums):
    left, right = -1, len(nums) 
        while True:
            left += 1
            while nums[left] == 0:
                left += 1
            right -= 1
            while nums[right] == 2:
                right -= 1
            if left >= right:
                return
            nums[left], nums[right] = nums[right], nums[left]

Answer 1

Целью разделения является не сортировка элементов, а разбиение (он же разбиение ) на две непустые группы, одна из которых содержит элементы меньше или равно элементу поворота и один, где элементы больше или равны элементу поворота. (Разделение Hoare позволяет любой группе содержать элементы, равные сводной, в то время как разделение Lomuto помещает все элементы, равные повороту, в правую группу. Быстрая сортировка может обрабатывать любой результат, но важно, чтобы ни одна группа не была пустой; в противном случае Быстрая сортировка может выполняться бесконечно без возможности разбить список на более мелкие части.)

Учитывая это, мы видим, что ваш пример вывода действителен: алгоритм останавливается в середине, а все значения слева половина меньше или равна 1, а все элементы в правой половине больше или равны 1. Порядок внутри разделов не имеет значения; Задача Quicksort состоит в том, чтобы на самом деле сортировать числа.

Однако у вашей реализации есть несколько проблем:

• Сравнение с 0 и 2 работает, если единственными значениями являются 0, 1, и 2. В общем случае вместо этого вам нужно сравнить значение элемента pivot.
• Таким образом, выбор кода должен быть встроен в ваш код. Это должен быть элемент в середине или слева от середины, если есть четное количество элементов.
• Вам необходимо вернуть right, который указывает, где находится разделение между двумя группами.