Попытка написать быструю сортировку и потратила некоторое время на отладку. Кажется, проблема во втором рекурсивном вызове, но я не могу понять, где я. Любой указатель будет потрясающим. Благодарю.
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 раза.
Так как вы получаете доступ к элементам на месте 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;
и функция вернется без замены двух элементов, даже если список явно не отсортирован.