Что не так с моим алгоритмом голландского национального флага?

Question

Я пытаюсь превратить массив следующим образом:

0, 1, 2, 2, 1, 0, 1, 0, 0, 1, 2

в это:

0 0 0 0 1 1 1 1 2 2 2

Вот мой код:

public static int[] sortDNF(int[] tape) {
    int smaller = 0; // everything with index < smaller is 0
    int bigger = tape.length - 1; // everything with index > bigger is 2
    int current = 0; // where we are looking now
    int tmp;

    while (current <= bigger) {
        if (tape[current] == 0) {
            tmp = tape[smaller];
            tape[smaller] = tape[current];
            tape[current] = tmp;
            smaller++;
        }
        if (tape[current] == 2) {
            tmp = tape[bigger];
            tape[bigger] = tape[current];
            tape[current] = tmp;
            bigger--;
        }
        current++;
    }

    return tape;
}

Вот что он производит:

 0  0  0  1  1  1  1  0  2  2  2 

В чем моя проблема?

Answer 1

Догадка:

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

current ++ должен выполняться только в случае ленты [current]! = 2. Это нормально делать, когда tape [current] = 0, потому что вы не изменили условие [меньший -> current] = 1-only. И это нормально для перемещения, когда tape [current] = 1, потому что это удовлетворяет условию «только 1».

... но я не пробовал.

Answer 2

Для тех, кто не изучал проблему, сортировки достаточно, чтобы найти решение, но это (или может быть) больше, чем необходимо. Решение проблемы DNF требует только того, чтобы все подобные предметы были перемещены вместе, но вам не нужно размещать неравные предметы в каком-либо определенном порядке.

Довольно легко решить DNF с ожидаемой сложностью O (N), где (в большинстве нормальных форм) сортировка имеет сложность O (N lg N). Вместо перестановки входных элементов гораздо проще просто посчитать элементы с любым заданным значением, а затем распечатать правильное число каждого. Поскольку порядок неравных элементов не имеет значения, вы обычно сохраняете свои значения в хеш-таблице.

Answer 3

Вам нужно увеличивать ток только во время проверки на 1 и проверки на 2. Когда вы проверяете на 3, вам просто нужно уменьшить больше.Здесь рабочий раствор.Кстати, это работает для массива значений между 1-3.Вы можете изменить его на 0-2, если хотите.

Программа выдает следующие выходные данные для массива случайных чисел следующим образом:

Исходный массив: [1, 3, 3, 3, 2, 2, 2, 1, 2, 2, 1, 3, 3, 2, 1, 1, 3]

Сортированный массив: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3]

private static int[] sortUsingDutchNationalFlagProblem(int[] array) 
{
    System.out.println("Original Array : " + Arrays.toString(array));
    int smaller = 0;    // everything with index < smaller is 1
    int bigger  = array.length - 1; // everything with index > bigger is 3
    int current = 0;        // where we are looking now
    int tmp;
    while (current <= bigger) {
            if (array[current] == 1) {
                    tmp            = array[smaller];
                    array[smaller] = array[current];
                    array[current] = tmp;
                    smaller++;current++;
            }
            if(array[current] == 2)
                current++;
            if (array[current] == 3) {
                    tmp            = array[bigger];
                    array[bigger]  = array[current];
                    array[current] = tmp;
                    bigger--;
            }
    }
    System.out.println("Sorted Array   : " + Arrays.toString(array));
    return array;
}

Answer 4

public static int[] sortDNF(int[] tape) {
    int smaller = 0; // everything with index < smaller is 0
    int bigger = tape.length - 1; // everything with index > bigger is 2
    int current = 0; // where we are looking now
    int tmp;

    while (current <= bigger) {
            if (tape[current] == 0) {
                    tmp = tape[smaller];
                    tape[smaller] = tape[current];
                    tape[current] = tmp;
                    smaller++;
            }
            else if (tape[current] == 2) {
                    tmp = tape[bigger];
                    tape[bigger] = tape[current];
                    tape[current] = tmp;
                    bigger--;
            }
            current++;
    }

    return tape;
}

Answer 5

Проблема в том, что вы отвечаете на (возможно, несуществующие) значения позже в цепочке, чтобы поменять местами неправильно пропущенные значения 1, попробуйте свой алгоритм в тривиальном случае:

1 2 0

2 поменялся местами в правильном месте, но текущий индекс был продвинут по сравнению с индексом 0, в результате чего:

1 0 2

Так что не увеличивайте ток, прежде чем проверять новое значение по этому индексу.

Answer 6

Вот мой подход с использованием Java

public static void dutchNationalFlagProblem(int[] input) {
    int low=0, mid=0, high = input.length -1;
    while(mid <=high) {
        switch (input[mid]) {
            case 0:
                swap(input, low++, mid++);  
                break;
            case 1:
                mid++;  
                break;
            default :
                swap(input, mid, high--);
                break;
        }
    }       
}

private static void swap(int[] input, int firstIndex, int secondIndex) {
    int temp = input[firstIndex];
    input[firstIndex] = input[secondIndex];
    input[secondIndex] = temp;

}

Вот соответствующие тестовые случаи

@Test
public void dutchNationalFlagProblemTest() {
    int[] input = new int[]{0,1,0,2,2,1};
    ArrayUtils.dutchNationalFlagProblem(input);
    assertThat(input, equalTo(new int[]{0,0,1,1,2,2}));
}

Answer 7

Я собираюсь предложить более простое решение: -)

public static int[] sortDNF(int[] tape) {
  Arrays.sort(tape);
  return tape;
}

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