быстрая сортировка — ошибка быстрой сортировки, возможно переполнение стека

Попытка написать быструю сортировку и потратила некоторое время на отладку. Кажется, проблема во втором рекурсивном вызове, но я не могу понять, где я. Любой указатель будет потрясающим. Благодарю.

void quickSort(vector<int> &list, int left, int right){

int pivot = left;
int temp = right;

if(left >= right - 1)
return;

while (left != right) {
if (pivot == left){
if (list[pivot] > list[right]) {
//-------------------------
int tempList = list[right];
list[right] = list[pivot];   // Swap for now
list[pivot] = tempList;
//-------------------------
pivot = right;
left++;
}else{
right--;
}

}else{
if (list[pivot] < list[left]) {
//-------------------------
int tempList = list[left];
list[left] = list[pivot];   // Swap for now
list[pivot] = tempList;
//-------------------------
pivot = left;
right--;
}else{
left++;
}
}
}
quickSort(list, 0, right-1);
quickSort(list, right + 1, temp);
}

Вот как я делаю набор данных прямо сейчас:

srand(time(0));
vector<int> list;
vector<int> sortedList;
int i;
for (i=0;i<10;i++) list.push_back(rand() %100);

Я получил набор данных 38 65 26 22 86 64 13 28 57 18

и получил выход 13 18 22 26 28 38 57 64 86 65

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

-1

Решение

Так как вы получаете доступ к элементам на месте right а также left Я предполагаю, что начальный вызов выглядит следующим образом:

quickSort(list, 0, list.size()-1);

Если список изначально инициализирован как vector<int>{ 2, 1 } первый звонок будет переведен в

quickSort(list, 0, 1);

С left=0 а также right=1 первый if-оценка будет оценивать

    if(0 >= 1-1)
return;

и функция вернется без замены двух элементов, даже если список явно не отсортирован.

0

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


По вопросам рекламы [email protected]