Алгоритм голландского национального флага с четырьмя цветами

Я запустил ваш код и понял, что ваш код переходит в бесконечный цикл, что позволяет вашей программе ничего не делать.

В основном методе вызывается sort0123(arr, arr_size);, а внутри этого метода while (mid <= hi), mid = 6 и hi = 9, что означает 6 <= 9, и по этой причине это условие бесконечно возвращает true из-за того, что оно всегда переходит к случаю 3 в какой-то момент и в случае 3 значения mid и hi не меняются.

Чтобы иметь возможность запускать свой код, вы должны изменить значение (я) mid и/или hi логически, и с этим ваша программа сможет вести себя так, как вы хотели.

Суть агрегации голландского флага в том, что всегда сохраняются инварианты. В таком состоянии, как 0000...11..XXX..222

1. lo всегда будет первой «1» (если она существует)
2. середина всегда будет первой неизвестной
3. привет всегда на последнем неизвестном

Для варианта с 4 цветами, предполагая, что вы сортируете в порядке 0,1,3,2, как это видно из кода, правила необходимо настроить следующим образом:

3. привет всегда на последнем 3
4. h2 всегда на последнем неизвестном

Следуя вышеизложенным правилам, код нужно будет изменить следующими способами:

while (mid <= h2)

. . .

case 2:
        {
            temp = a[mid];
            a[mid] = a[hi];
            a[hi] = temp;

            hi--;
            h2--;
            break;
        }
case 3:{
            temp = a[mid];
            a[mid] = a[h2];
            a[h2] = temp;
            h2--;
            break;

        }

Для сортировки в порядке 0,1,2,3 просто поменяйте местами операторы case '2' и '3'.

PS: Пожалуйста, сделайте вопрос описательным, чтобы помочь людям легко понять проблему.

Вот мое решение, написанное на питоне. Обоснование этого заключается в том, чтобы сжать четвертый цвет (средний правый цвет) между средним левым и правым подмассивами. Он определяет цвета по мере выполнения алгоритма.

Он имеет временную сложность O (n) и пространственную сложность O (1).

from typing import List

def dutch_variant_four_colors(array: List[int]) -> List[int]:
    left = array[0]
    mid_left = None
    right = None

    left_i = 0
    mid_left_i = 0
    mid_right_i = len(array)
    right_i = len(array)

    while mid_left_i < right_i and mid_left_i < mid_right_i:
        if (array[mid_left_i] == left):
            array[mid_left_i], array[left_i] = array[left_i], array[mid_left_i]
            mid_left_i += 1
            left_i += 1
        elif (right is None or array[mid_left_i] == right):
            right_i -= 1
            mid_right_i = right_i
            array[mid_left_i], array[right_i] = array[right_i], array[mid_left_i]
            right = array[right_i]
        else:  # it is a mid value
            if (mid_left is None):
                mid_left = array[mid_left_i]
            if (array[mid_left_i] == mid_left):
                mid_left_i += 1
            else:
                mid_right_i -= 1
                array[mid_left_i], array[mid_right_i] = array[mid_right_i], array[mid_left_i]

    return array


# Sample usages
print(dutch_variant_four_colors([1,1,3,3,4,3,2,2]))
print(dutch_variant_four_colors([1,2,3,4,2,3,1,3]))
print(dutch_variant_four_colors([1,2,3,4,4]))
print(dutch_variant_four_colors([0,1,2,5,5,2,2,0]))
print(dutch_variant_four_colors([1,0,3,0,5,5]))
print(dutch_variant_four_colors([1,2,3,2,5,1,1,3]))
print(dutch_variant_four_colors([5,1,2,3,2,1,1,3]))
print(dutch_variant_four_colors([3,2,5,1]))
print(dutch_variant_four_colors([3,2,1,5]))
print(dutch_variant_four_colors([3,2,1,3,5,2,2,1,2,3,5,3,2,1,3,5,3,3,2,2,2,5,5,5,3,3,2,5,3,1,2,3,2,1,3,2,1,1,2,3,2,3,2,1,2,3,2,1,2,3,2,2,2,2,2,3,3,3,1,2,2,1,1,2,3]))

Gist доступен на https://gist.github.com/lopespm/81a336871ce6074f63f3cad349c3a95d

Мое решение в ideone

#include <iostream>
using namespace std;



void DutchNationalFlag4(int * arr , int n )
{
    int low = 0 , mid1 = 0 , mid2 = n- 1 , high = n-1 ;
    int temp;
 
    // This type of problems are best solved by using invariants 
 
    // arr[ 0 .. low -1 ] conatins 0
    // arr[ low .. mid1 -1 ] contains 1
    // arr[ mid1 .. mid2 ] is unknown
    // arr[ mid2 + 1 ... high - 1 ] contains 2
    // arr[ high .. n-1 ] contains 3
 
    // termination condition : Evert Iteration unkown length decreases so eventually will be Zero
    while( mid1 <= mid2 )
    {
        switch( arr[ mid1 ])
        {
            case 0 :
            {
                std::swap( arr[ low ] , arr [ mid1 ] );
                low ++ ;
                mid1 ++;
                break;
            }
 
            case 1 :
            {
                mid1 ++;
                break;
            }
 
            case 2 :
            {
                std::swap( arr[ mid1 ] , arr[ mid2 ]);
                mid2 -- ;
                break;
            }
 
            case 3 :
            {
                std::swap( arr[ mid1 ] , arr[ mid2 ]);
                std::swap( arr[ mid2 ] , arr[ high ]);
                mid2 --;
                high --;
                break;
            }
 
        }
    }
 
    for( int i =0 ; i < n ; i++)
    {
        cout << arr[ i ] << " " ;
    }
}
 
int main() 
{
    int arr[] = {1,2,3,0,2,1,3,0,2,1,0,1,3,1,0,2,1,0};
    int n = sizeof(arr) / sizeof(arr[0]) ;
    DutchNationalFlag4(arr , n );
    return 0;
}

Я решил это в приведенной выше ссылке! Ваше здоровье

Пожалуйста, постарайтесь быть более ясным, когда вы задаете вопрос. А также убедитесь, что ваши переменные либо названы интуитивно понятно, либо вы предоставили соответствующие комментарии. Честно говоря, меня смутили hi и h2, mid!