Быстрая сортировка выполняется неправильно

Question

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

Я просматривал каждую строку несколько раз и не вижу, что не так.Все имеет смысл для меня.

static <E extends Comparable<? super E>>
void quicksort(E[] A, int low, int high) {
    if (low < high) {
        int pivotIndex = (low + high) / 2;
        E pivot = A[pivotIndex];
        // move pivot to end
        A[pivotIndex] = A[high];
        A[high] = pivot;

        int i = low - 1;
        int j = high;
        do {
            do {
                i++;
            } while (A[i].compareTo(pivot) < 0);
            do {
                j--;
            } while ((A[i].compareTo(pivot)) > 0 && (j > low));
            if (i < j) {
                E swap = A[i];
                A[i] = A[j];
                A[j] = swap;
            }
        } while (i < j);
        // i is now the first spot in the right partition (where we will put pivot)
        // now put pivot back where it belongs
        A[high] = A[i];
        A[i] = pivot;
        quicksort(A, low, i - 1); // sort left partition
        quicksort(A, i + 1, high);
    }
}

Я ожидал [2, 3, 5, 6, 10, 101, 200, 300], но получил [3, 5, 2, 6, 10, 101, 200, 300]

Answer 1

Сравнение во втором внутреннем цикле использует A [i] для сравнения, когда оно должно использовать A [j]:

            } while ((A[j].compareTo(pivot)) > 0 && (j > low));  // A[j] not A[i]

---

Альтернативный вариант для этого типа быстрой сортировкине меняет шарнир на A [high], и, оставляя шарнир в середине, код не должен будет проверять наличие j> low во втором внутреннем цикле, который немного быстрее.Использование этого варианта требует других изменений: от init j до high + 1, и два рекурсивных вызова должны быть быстрой сортировкой (A, low, j) и быстрой сортировкой (A, j + 1, high).Обратите внимание, что значения, равные Pivot, включая саму Pivot, могут оказаться в любом из разделов, поскольку значения, равные Pivot, меняются местами.

Пример кода для примитивов (int), который использует рекурсию для меньшей или равной части, а затем выполняет итерацию назад для большей части, чтобы избежать переполнения стека в худшем случае.Может быть преобразован для использования универсального объекта E.

    public static void qsort(int[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            int p = a[md];
            int t;
            while(true){
                while(a[++ll] < p);
                while(a[--hh] > p);
                if(ll >= hh)
                    break;
                t     = a[ll];
                a[ll] = a[hh];
                a[hh] = t;
            }
            ll = hh++;
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }