Быстрый поиск Сортировка по убыванию Не возрастанию

Question

Я только что реализовал алгоритм QuickSort из книги и получил странный результат. Он работает, но он сортируется в порядке убывания, а не возрастает. Например: [1, 5, 2, 10, 6, 9, 8, 3, 7, 4] сортируется [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] чтобы найти источник в моем коде:

private void quicksort(int[] A, int p, int r) { 
    if (p < r) { 
     int q = partition(A, p, r); 
     quicksort(A, p, q); 
     quicksort(A, q + 1, r); 
    } 
} 

private int partition(int[] A, int p, int r) { 
    int x = A[p]; // pivot 
    int i = p; 
    int j = r; 
    while (true) { 

     while (A[i] > x) { 
      i++; 
     } 

     while (A[j] < x) { 
      j--; 
     } 
     if (i < j) { 
      int temp = A[i]; 
      A[i] = A[j]; 
      A[j] = temp; 
     } else { 
      return j; 
     } 
    } 
} 

ИСХОДНЫЙ CALL:

quicksort(A, 0, A.length - 1); 

как я вычислить сложность пространства для сортировки?

спасибо ребята

Answer 1

Это в вашей функции раздела, вы сортировки в порядке убывания.

while(true) { 
//ignore all the numbers greater than X to left 
while (A[i] > x) { 
     i++; 
    } 
//ignore all numbers lesser than X to right 
while (A[j] < x) { 
     j--; 
} 

//swap a number lesser than X on left with a number greater than X on right 
    if (i < j) { 
     int temp = A[i]; 
     A[i] = A[j]; 
     A[j] = temp; 
     i++; 
     j--; 
    } else { 
     //Now the array is so sorted, that all numbers lesser than X are on right of it and greater than X are to left of it. Hence return position of X 
     return j; 
    } 
} 

// для восходящих:

while(true) { 

while (A[i] < x) { 
     i++; 
} 

while (A[j] > x) { 
     j--; 
} 

    if (i < j) { 
     int temp = A[i]; 
     A[i] = A[j]; 
     A[j] = temp; 
     i++; 
     j--; 
    } else { 
     return j; 
    } 
}