Алгоритм быстрой сортировки для сортировки массива с использованием Hoare Partitioning в Java - PullRequest
Новая
       7

Алгоритм быстрой сортировки для сортировки массива с использованием Hoare Partitioning в Java

0 голосов
/ 18 марта 2020

Я пытаюсь отсортировать этот массив быстрой сортировкой: 

int[] arr = {25,23,21,29,28,22,24,27};

Моя функция быстрой сортировки: 

public static void quickSort(int[] arr) { // sorts array using quick sort algorithm
    if (arr[0] < arr[arr.length-1]) {
        int s = hoarePartitioning(arr);
        quickSort(Arrays.copyOfRange(arr, 0, s-1));
        quickSort(Arrays.copyOfRange(arr, s+1, arr.length));
    }
}

Я использовал Hoare Partitioning: 

public static int hoarePartitioning(int[] arr) {
    int pivot = arr[0];
    int i = 0;
    int j = arr.length;
    do {
        do {i++;} while(pivot >= arr[i] && i < arr.length);
        do {j--;} while(pivot <= arr[j] && j >= 0);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }while(i <= j);

    int temp = arr[i];  //undo last swap when i >= j
    arr[i] = arr[j];
    arr[j] = temp;

    temp = arr[0];
    arr[0] = arr[j];
    arr[j] = temp;

    return j;
}

Однако, когда я распечатываю массив, это результат: 

22 23 21 24 25 28 29 27

Моя функция разбиения Hoare работает нормально, но я до сих пор не понимаю, почему массив не отсортирован. Что я здесь не так делаю? Спасибо.

Ответы [ 2 ]

1 голос
/ 18 марта 2020

Метод quicksort в корне неверен: 

    quickSort(Arrays.copyOfRange(arr, 0, s-1));
    quickSort(Arrays.copyOfRange(arr, s+1, arr.length));

Каждый раз, когда вы выполняете рекурсию, вы создаете новые массивы для левого и правого подмассивов, (пытаетесь) отсортировать новые массивы, а затем выбросить их . Net результат: исходный массив не изменяется.

Не копировать подмассивы. Передайте исходный массив вместе с началом и концом подмассива, который будет отсортирован в каждом рекурсивном вызове. При необходимости используйте вспомогательную функцию; например, 

 public void quicksort(int[] array) {
     quicksort(array, 0, array.length - 1);
 }

 public void quicksort(int[] array, int start, int end) {
     ...
 }

Есть и другие проблемы:

  1. Тест if выглядит неправильно. Зачем вам пропустить сортировку массива / подмассива в этом состоянии? Фактический тест должен проводиться по размеру сортируемого подмассива ... а не содержимого подмассива.

  2. Вычисления верхних границ для подмассива выглядят неверно; s - 1 является включающей границей, но arr.length является исключительной границей. Один из них должен быть не прав.

0 голосов
/ 18 марта 2020

Generi c Код раздела Hoare как отдельная функция. Использование среднего значения для сводной диаграммы позволяет избежать сложности времени O (n ^ 2) в худшем случае для уже отсортированных или обратно отсортированных данных. Любой элемент, кроме [hi], может быть использован как точка с этим указанным c кодом. Нет необходимости ограничивать проверку индексов границами, потому что в худшем случае, достижение точки поворота остановит начальные внутренние циклы, а любой обмен позволит внутренним циклам повторяться без проверки границ. 

    public static void qsort(int[] a, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int  p = a[lo+(hi-lo)/2];
        int  i = lo-1;
        int  j = hi+1;
        int t;
        while(true){
            while(a[++i] < p);
            while(a[--j] > p);
            if(i >= j)
                break;
            t     = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        qsort(a, lo, j);
        qsort(a, j+1, hi);
    }
...