Метод итеративной быстрой сортировки

Question

Я пытаюсь реализовать метод быстрой сортировки hoare, который выполняется итеративно. Я использую алгоритм ниже. Так что сейчас он вводит: 10 7 8 9 1 5 и, например, когда я запускаю, он выводит: 5 7 8 9 1 10 он переключает только 2 элемента из массива. Почему это останавливается? Где я go ошибся?

Алгоритм:

1. Создание массивов слева и справа от N / 2 элементов, где число N элементов в массиве a.
2. Назначьте left [0] на 0 и right [0], чтобы индексировать последний элемент массива a (N-1). Присвойте переменной stackpos значение 1.
3. Уменьшите значение переменной stackpos на 1. Дайте левому [stackpos] значение l и правому [stackpos] значение r
4. . Присвойте медианное значение переменной m. Медианы должны быть выбраны между элементами от a [l] до a [r].
5. Присвоить значение переменной l переменной i и присвоить r переменной j.
6. Если a [i] меньше m, увеличьте i.
7. Если a [j] больше m, уменьшите j.
8. Если переменная i меньше или равна j, то: a) Поменять местами элементы a [i] и a [j] с использованием принципа трех чашек. б) увеличить я на один. c) Уменьшите j на единицу.
9. Если i меньше или равно j, вернитесь к шагу 6. ​​
10. Если i меньше r, то: a) Назначьте left [stackpos ] для меня. б) Дайте r [стэкпос] r. c) Увеличьте значение переменной стека на 1.
11. Присвойте значение переменной r переменной j.
12. Если переменная l меньше r, вернитесь к шагу 4.
13. Если переменная stackpos больше 0, вернитесь к шагу 3

Код:

public static void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static int median (int []a) {
    int rnd = new Random().nextInt(a.length);
    int M = a[rnd];
    return M;
}

private static int partition(int[] a, int i, int M, int j) {
    while (i <= j) {
        while (a[i] < M) {
            i++;
        }
        while (a[j] > M) {
            j--;
        }
        if (i <= j) {
            swap(a,i, j);
            i++;
            j--;
        }
    }
    return i;
}

public static int[] secondMethod(int[] a) {
    int N=a.length;
    int left [] = new int [N/2];
    int right [] = new int [N/2];
    left[0]=0;
    right[0]=a[N-1];

    int stackpos = 1;
    stackpos--;
    int I = left[stackpos];
    int r = right[stackpos];

    int M=median(a);

    int i=I;
    int j=r;

    partition(a,i,M,j);

    if (i<=j) {
        while (a[i] < M) {
            i++;
        }
    }

    if (i<r) { //10.
        left[stackpos]=i;
        right[stackpos]=r;
        stackpos++;
    }
    r=j;  //11.
    if (I<r) {
        while(true) {
            M = median(a);
            break;
        }
    }

    if (stackpos>0) {
        while(true) {
            stackpos--;
            I = left[stackpos];
            r = right[stackpos];
            break;
        }
    }
    return a;
}

public static void main(String[] args) {
  int []a = {10, 7, 8, 9, 1, 5};
  a = secondMethod(a);
  System.out.println("result :");
  for (int i = 0; i <  a.length; i++)
    System.out.print(a[i] + " ");
  }
}

Answer 1

Некоторые вещи здесь не так.

right[0]=a[N-1];   # <-------------- pretty sure this should just be N-1, not a[N-1]

Второе, может быть, еще хуже, то, что раздел вызывается только один раз .

Вам нужно подумать об этом все до конца То, как вы объясняете свой алгоритм и циклы while (true), из которых вы немедленно выходите, делает это очевидным.

Мой совет: сначала выполните рекурсивную быструю сортировку, чтобы ознакомиться с алгоритмом. Также, чтобы выйти из вашего итеративного мышления. Затем ознакомьтесь с общими методами преобразования рекурсивных методов в итерационные (стеки, динамическое программирование c). Затем примените то, что вы узнали, к быстрой сортировке.

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