Я пытаюсь реализовать QuickSort в Java, но не могу получить вывод?

Question

Я пытаюсь реализовать QuickSort, взяв последний элемент в качестве опоры. Но я не могу сделать правильный вывод.

Кроме того, какие изменения необходимо сделать, чтобы сделать его рандомизированным? Я кодирую на Java.

public class QuickSortDemo {
    public static void quicksort(int A[], int temp[], int left, int right) {
        int q, i;

        //why u need to check this  base case always
        if (left < right) {
            q = partition(A, temp, left, right);
            quicksort(A, temp, left, q - 1);
            quicksort(A, temp, q + 1, right);

            for (i = 0; i < A.length; i++) {
                System.out.println(A[i]);
            }
        }
    }

    public static int partition(int A[], int temp[], int left, int right) {
        int x, i, j;

        x = A[right];
        i = left - 1;

        for (j = left; j <= right - 1; j++) {
            if (A[j] <= x) {
                i = i + 1;
                A[i] = A[j];
            }
        }

        A[i + 1] = A[right];
        return i + 1;
    }

    public static void main(String s[]) {
        int ar[] = {6, 3, 2, 5, 4};
        int p[] = new int[ar.length];
        quicksort(ar, p, 0, ar.length - 1);
    }
} //end class QuickSortDemo

OutputShown

2

2

4

5

4

2

2

4

4

4

2

2

4

4

4

Answer 1

Как уже упоминалось в комментариях, в методе разбиения есть некоторые ошибки. При реализации быстрой сортировки вы хотите поменять местами элементы в массиве, а не просто перезаписать элементы в передней части. Они будут потеряны.

Кроме того, код начинается слева и всегда меняет местами каждый элемент, который меньше или равен оси. Это ненужные операции, если элемент уже находится в правильной части массива.

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

Стандартная реализация (что я знаю) будет выглядеть примерно так

public static int partition(int A[], int left, int right) {
    int pivot, i, j;

    pivot = A[right];
    i = left;
    j = right - 1;

    do {
        // Search for element greater than pivot from left, remember position
        while ( A[i] <= pivot && i < right ) i++;

        // Search for element less than pivot from right, remember positon
        while ( A[j] >= pivot && j > left ) j--;

        // If elements are in the wrong part of the array => swap
        if ( i < j ) swap( A, i, j );

    // Continue until the whole (sub)array has been checked    
    } while ( j > i );

    // Put the pivot element at its final position if possible
    if ( A[i] > pivot )
        swap ( A, i, right );

    // Return the border / position of the pivot element    
    return i;
}

Своп как обычно

public static void swap(int[] A, int first, int second) {
    int temp = A[first];
    A[first] = A[second];
    A[second] = temp;
}

Также обратите внимание, что нет необходимости использовать temp в этом коде. Ваш код объявляет это в своих подписях, но никогда не использует это.

Answer 2

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

 public class QuickSortDemo {
    public static void main(String[] args) {
    int[] input = {6, 3, 2, 5, 4};
    int[] output = quickSort(input, 0, input.length-1);
    for(int a : output) {
    System.out.println(a);
    }}
    public static int[] quickSort(int[] array, int lowerIndex, int higherIndex) {

     int i = lowerIndex;
     int j = higherIndex;
     // calculate pivot number, rightmost value
     int pivot = array[higherIndex];
     // Divide into two arrays
     while (i <= j) {
     while (array[i] < pivot) {
     i++;
     }
     while (array[j] > pivot) {
     j--;
     }
     if (i <= j) {
     int temp = array[i];
     array[i] = array[j];
     array[j] = temp;
     //move index to next position on both sides
     i++;
     j--;
     }
     }
     // call quickSort() method recursively
     if (lowerIndex < j)
     quickSort(array,lowerIndex, j);
     if (i < higherIndex)
     quickSort(array, i, higherIndex);

     return array;
     }
    }