алгоритм быстрой сортировки не сортировки конечного элемента?

Question

У меня есть этот код, который я написал, используя алгоритм, я нашел в Википедии:

public static void quicksort(int[] arr, int low, int hi) 
    { 
     if(low < hi) 
     { 
      int pivot = part(arr, low, hi); 
      quicksort(arr, low, pivot - 1); 
      quicksort(arr, pivot + 1, hi); 
     } 
    } 
    public static int part(int[] arr, int low, int hi) 
    { 
     int pivot = arr[hi]; 

     int i = low; 
     for(int j = low; j < hi - 1; j++) 
     { 
      if(arr[j] <= pivot) 
      { 
       swap(arr, i, j); 
       i++; 
      } 
     } 
     swap(arr, i, hi); 
     return i; 
    } 

    public static void swap(int[] ar, int a, int b) 
    { 
     int temp = ar[a]; 
     ar[a] = ar[b]; 
     ar[b] = temp; 
    } 

Учитывая этот вход:

31, 5, 5, 5, 5, 4, 4, 4, 5, 4 

следует ожидать, чтобы получить:

4, 4, 4, 4, 5, 5, 5, 5, 5, 31 

, но вместо того, чтобы Я получаю:

4, 4, 4, 4, 5, 5, 5, 5, 31, 5 

Что дает?

Я называю первоначальный вид с: quicksort(array, 0, array.Length - 1);

Answer 1

Если вы вызываете его с помощью Length - 1, то этого цикла:

for (int j = low; j < hi - 1; j++) 

..should быть:

for (int j = low; j <= hi ; j++)