Внедрение в Java псевдокода быстрой сортировки на Википедии

Question

Я использую псевдокод, называемый схемой разбиения Lomuto на https://en.wikipedia.org/wiki/Quicksort. Но я просто не понимаю, что я делаю здесь неправильно. Массив никогда не организуется (независимо от размера ввода). Это подготовка к моему итоговому экзамену. Мой профессор хочет, чтобы мы использовали этот алгоритм, но я не могу просто изучить его, пока не пойму, как он работает, протестировав его.

private static void quickSort(Integer A[], int l, int r) {

    if (l < r) {
        int k = partition(A, l, r);
        quickSort(A, l, k - 1);
        quickSort(A, k + 1, r);
    }
}

private static int partition(Integer A[], int l, int r) {
    int pivot = A[r];
    int i = l;

    for (int j = l; j <= r - 1; j++) {
        if (A[j] <= pivot) {
            i++;
            int temp = A[j];
            A[j] = pivot;
            pivot = temp;
        }
    }

    int temp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp;

    return i + 1;
}

Answer 1

Я не знаю, что еще сказать, кроме того, что вы просто неправильно расшифровали псевдокод. В начале partition, i должен равняться l - 1, но вы установили его на l,

Кроме того, вы не обмениваетесь A[i] с A[j] в рамках вложенного цикла. Вот правильная реализация:

private static int partition(Integer A[], int l, int r) {
    int pivot = A[r];
    int i = l - 1;

    for (int j = l; j <= r - 1; j++) {
        if (A[j] < pivot) {
            i++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }

    int temp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp;

    return i + 1;
}