Понимание голландской программы национального флага

Question

Я читал проблему голландского национального флага, но не мог понять, что low а также high аргументы в threeWayPartition функция в реализации C++.

Если я принимаю их как минимальные и максимальные элементы массива для сортировки, то if а также else if заявления не имеет никакого смысла, так как (data[i] < low) а также (data[i] > high) всегда возвращает ноль.

Где я не прав?

Answer 1

low а также high это значения, которые вы определили для трехстороннего разбиения, т.е. для трехстороннего разбиения вам нужны только два значения:

[bottom] <= low  < [middle] < high <= [top]

В программе на C++ вы перемещаете позиции, в которых произошли разбиения. Пошаговый пример:

data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ]
low  = 4
high = 8

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
p^  i^                                  q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
    p^  i^                              q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^  i^                          q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^      i^                      q^

   [ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ]
        p^      i^                  q^

   [ 3 , 1 , 0 , 4 , 8 , 2 , 6 , 9 , 9 ]
            p^      i^              q^

   [ 3 , 1 , 0 , 4 , 9 , 2 , 6 , 8 , 9 ]
            p^      i^          q^

   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^      i^      q^

   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^          i^  q^

   [ 3 , 1 , 0 , 2 , 6 , 4 , 9 , 8 , 9 ]
                p^         iq^

Как говорит алгоритм:

• Поменяйте местами элемент над дном (т.е. p + 1) потому что все ниже дна уже проверено, или
• Поменяйте местами элемент под верхом (т.е. q - 1) потому что все выше вершины уже проверено, или
• Оставьте элемент там, где он есть, потому что он принадлежит середине.

Ты получаешь [3, 1, 0, 2], [6, 4] а также [9, 8, 9] как нижний, средний и верхний разделы соответственно.

Answer 2

} else if (data[i] >= high) { показывает, что то, что вы, хотя и видели, может не соответствовать тому, что было написано в статье.

Answer 3

Думать о low а также high как полуоткрытый диапазон [low,high) для значений в среднем разделе. Все значения меньше чем low в конечном итоге в левом разделе. Средний раздел будет содержать значения из low до, но не включая, high, Наконец, все значения больше или равны high в конечном итоге в правильном разделе.