Quicksort: wikipedia-реализация не работает

Question

Я просто попытался реализовать алгоритм быстрой сортировки из википедии (https://en.wikipedia.org/wiki/Quicksort), но чего-то не хватает. Вот мой код:

public static void quicksort(int[] a, int lo, int hi) { 
    if(lo < hi) { 
     int p = partition(a, lo, hi); 
     quicksort(a, lo, p - 1); 
     quicksort(a, p + 1, hi); 
    } 
} 

public static int partition(int[] a, int lo, int hi) { 
    //choose pivot element 
    int pivotIndex = 0; 
    int pivotVal = a[pivotIndex]; 

    //put pivot at the end of array 
    swap(a, pivotIndex, hi); 

    //compare other elements to pivot and swap accordingly 
    int storeindex = lo; 
    for(int i = lo; i < hi; i++) { 
     if(a[i] <= pivotVal) { 
      swap(a, i, storeindex); 
      storeindex++; 
     } 
     //set pivot in right place of array 
     swap(a, storeindex, hi); 
    } 

    return storeindex; //return 
} 

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

А вот пример того, что происходит не так:

int[] a = {1,2,3,4,5}; 
quicksort(a, 0, a.length - 1); 

возвращается: 1, 2, 3, 5, 4 вместо того, что он должен: 1, 2, 3, 4, 5

Я смотрел на это довольно долгое время, и я был бы очень признателен, если бы кто-то помог мне выяснить, где я ошибся :) Спасибо!

Answer 1

две проблемы:

1. Вы должны выбрать значение поворота от раздела, а не просто взять первый элемент массива

2. Последняя замена должна быть вне цикла, вы ставите поворотный элемент к его месту после прохождения перегородки. Смотри последние две строки:

Фиксированный метод раздела:

public static int partition(int[] a, int lo, int hi) { 
    //choose pivot element 
    int pivotIndex = lo; // ERROR 1 fixed 
    int pivotVal = a[pivotIndex]; 

    //put pivot at the end of array 
    swap(a, pivotIndex, hi); 

    //compare other elements to pivot and swap accordingly 
    int storeindex = lo; 
    for (int i = lo; i < hi; i++) { 
     if (a[i] <= pivotVal) { 
      swap(a, i, storeindex); 
      storeindex++; 
     } 
    } 

    //set pivot in right place of array 
    swap(a, storeindex, hi); // ERROR 2 fixed 
    return storeindex; //return 
}