quicksort не работает правильно

Question

Я не могу найти проблему в своем коде. Он работает, но он не может правильно отсортировать массив. Я думаю, что часть, которая меня больше всего смущает, заключается в том, как передать несортированный субарер в рекурсивный процесс.

#include<iostream> 
using namespace std; 

void quickSort(int*, int, int); 
int partition(int*, int, int); 

int main(){ 
    int const size = 10; 
    int a[size] = {37, 2, 6, 4, 89, 8, 10, 12, 68, 45}; 

    for(int i=0; i<size; i++){ 
     cout << a[i] << " "; 
    } 
    quickSort(a, 0, size-1); 
    cout << endl; 
    for(int i=0; i<size; i++){ 
     cout << a[i] << " "; 
    } 

} 

void quickSort(int *array, int start, int end){ 
    if(start<end){ 
     int piv = partition(array, start, end); 
     quickSort(array, 0, piv-1); 
     quickSort(array, piv+1, end-1); 
    } 
} 

int partition(int *array, int start, int end){ 
    int piv = array[start]; 
    int i = start+1; 
    int j = end; 
    while(i<j){ 
     while(array[i]<piv and i<end) i++; 
     while(array[j]>piv) j--; 
     if(i<j){ 
      int temp = *(array+i); 
      *(array+i) = *(array+j); 
      *(array+j) = temp; 
     } 

    } 
    int temp = *array; 
    *array = *(array+j); 
    *(array+j) = temp; 
    return j; 
} 

Выход таков:

37 2 6 4 89 8 10 12 68 45 
    4 6 8 10 12 37 68 89 2 45 

Answer 1

Помните, что end является включительно, так что вы не должны быть рекурсии на end-1, но end.

Ваш partition() функция делает несколько ошибок:

• В вашем вложенная в то время как цикл, вы должны проверять, что i<j, не i<end.
• В ваших вложенных петлях, вы должны сначала проверить, что i<j и только затем сравнить элемент с piv.
• После ваших циклов вы должны проверить, соответствует ли j элемент>piv или нет. Если это так, вам необходимо уменьшить j перед выполнением свопа. Рассмотрим:

 
    37 2 6 4 12 8 10 89 68 45 
         j 
    89 2 6 4 12 8 10 37 68 45 

• После ваших петель, ты всегда своп с первого элемента во всем массиве. Я уверен, что вы означали для обмена с array[start].

Кстати, *(array+j) - это то же самое, что и array[j].

Надеюсь, это поможет.

Answer 2

Первое, что я заметил, что:

quickSort(array, 0, piv-1); 
    quickSort(array, piv+1, end-1); 

должно быть:

quickSort(array, start, piv-1); // start, not 0 
    quickSort(array, piv+1, end); // end, not end-1 

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

void quickSort(int *array, int start, int end){ 

    if(start<end){ 
     cout << "Before sort: "; 
     for(int i=start; i<=end; i++){ 
      cout << array[i] << " "; 
     } 
     cout << std::endl; 
     int piv = partition(array, start, end); 
     std::cout << "Pivot index: " << piv << ", Pivot element: " << array[piv] << std::endl; 
     quickSort(array, start, piv-1); 
     quickSort(array, piv+1, end); 
    } 

    cout << "After sort: "; 
    for(int i=start; i<=end; i++){ 
     cout << array[i] << " "; 
    } 
    cout << std::endl; 
} 

С теми, я получил следующий вывод:

37 2 6 4 89 8 10 12 68 45 
Before sort: 37 2 6 4 89 8 10 12 68 45 
Pivot index: 6, Pivot element: 37 
Before sort: 10 2 6 4 12 8 
Pivot index: 4, Pivot element: 10 
Before sort: 8 2 6 4 
Pivot index: 3, Pivot element: 8 
Before sort: 4 2 6 
Pivot index: 1, Pivot element: 4 
After sort: 2 
After sort: 6 
After sort: 2 4 6 
After sort: 
After sort: 2 4 6 8 
After sort: 12 
After sort: 2 4 6 8 10 12 
Before sort: 89 68 45 
Pivot index: 9, Pivot element: 2 
Before sort: 89 68 
Pivot index: 8, Pivot element: 45 
After sort: 89 
After sort: 
After sort: 89 45 
After sort: 
After sort: 89 45 2 
After sort: 68 4 6 8 10 12 37 89 45 2 
68 4 6 8 10 12 37 89 45 2 

Это привело меня приглядеться в partition, и я заметил, что у вас есть:

int temp = *array; 
*array = *(array+j); 
*(array+j) = temp; 

Это объясняет, почему число из нижней половины секционированного массива было втянуто в верхнюю половину секционированного массива.Они должны быть:

int temp = *(array+start); 
*(array+start) = *(array+j); 
*(array+j) = temp; 

Это более читаемым мне использовать:

int temp = array[start]; 
array[start] = array[j]; 
array[j] = temp; 

С этими изменениями, массив вышел отсортированный.