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

Question

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

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

#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

-1

c++partition pivot pointers quicksort

Решение

Другие решения

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

    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;

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

0

Источник

Accepted Answer

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

Ваш partition() Функция делает пару ошибок:

В вашем вложенном цикле while вы должны проверять, что i<jне i<end,
В ваших вложенных циклах while следует первый Проверь это 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],

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

0