Ошибка алгоритма быстрого сортировки

Question

Проблема с моим алгоритмом быстрой сортировки. Код компилируется без каких-либо ошибок, но когда я пытаюсь запустить программу, единственным выходом, который я получаю, является «Случайные числа:», а затем действует так, как будто хочет ввода от пользователя, а затем мне нужно убить программу. Теперь, когда я удаляю вызов моей функции quicksort в моей основной программе, программа выводит цифры, но не работает с вызовом функции quicksort. Я не уверен, являются ли параметры, которые я использую, проблемой, или если это сама функция.

#include <iostream> 
#include <stdlib.h> 
#include <iomanip> 
#include <stack> 
#include <queue> 
using namespace std; 

void quicksort(int arr[], int left, int right) { 
    int l = left; 
    int r = right; 
    int tmp; 
    int pivot = arr[(left + right)/2]; 

    while (l <= r) { 
    while (arr[l] < pivot) 
     l++; 
    while (arr[l] > pivot) 
     r--; 
    if (l <= r) { 
     tmp = arr[l]; 
     arr[l] = arr[r]; 
     arr[r] = tmp; 
     l++; 
     r--; 
    } 
    } 

    if (left < r) 
    quicksort(arr, left, r); 
    if (l < right) 
    quicksort(arr, r, right); 

} 

int main() { 
    int n = 20; 
    int testlist[n]; 

for (int i = 0; i<n; i++) { 
    testlist[i] = rand()%100; 
} 

cout << "The random numbers are: " << endl; 
for (int i = 0; i < n; i++) cout << testlist[i] << " "; 


quicksort(testlist, 0, n - 1); 

cout << " " << endl; 

cout << "The sorted numbers are: " << endl; 
for (int i = 0; i < n; i++) { 
    cout << testlist[i] << " "; 
} 

return 0; 

} 

Answer 1

Это происходит потому, что что-то идет не так внутри quicksort() и печати номера без std::endl!

Вы видите, что без std::endl цифры записываются в выходной буфер, но они не размыты. В конечном итоге они будут без std::endl, но ваш код не сделает это к тому времени.

Pro tip: Всегда используйте std::endl при отладке кода!

---

Я не буду отлаживать quicksort(), так как вы должны сделать это для того, чтобы практике! Если вам нужна ссылка, вы всегда можете использовать пример моего ребенка: Quicksort (C++), который написан в стиле c, так что люди из c и c++ могут легко следовать! :)

---

Hunch: Вы можете использовать рекурсию, ваша программа не завершается ... Бесконечный цикл может быть причиной ...;)

---

BTW, если я вам и не было ни одной важной причины для использования:

#if __INCLUDE_LEVEL__ < 1 

Я бы отбрасывать, что (наряду с сопровождаемого #endif).

Answer 2

У вас есть бесконечный цикл в вашей функции quicksort. Поскольку эта функция никогда не возвращается, ничто после строки «Случайные числа:» не печатается, так как вызовникогда не возвращается. Сами случайные числа могут или не могут печатать (и выполнять печать в моей системе), так как система не гарантирует немедленного сброса выходного буфера на экран. (Они, вероятно, будет напечатан, если вы написали std::endl к cout после того, как цикл, который печатает число.)

Я подозреваю, что это проблема:

while (arr[l] > pivot) 
    r--; 

Это заявление while (arr[l] > pivot), вероятно, следует быть на самом деле while (arr[r] > pivot).