Я не уверен, что не так с моим кодом, но в строке 30, когда начинается рекурсия, моя программа прерывается и выводит только несортированный массив, а алгоритм быстрой сортировки никогда не завершается. Если кто-нибудь знает, почему эта программа не работает правильно, пожалуйста, дайте мне знать. Заранее спасибо.
#include <iostream>
#include <time.h>
using namespace std;
void quickSort(int qarray[], int l, int r){
int i = l, j = r;
int temp;
int pivot = qarray[(l+r)]/2;
//partitioning
while(i<=j){
while(qarray[i]< pivot)
i++;
while(qarray[j] > pivot)
j--;
if(i<=j){
temp = qarray[i];
qarray[i] = qarray[j];
qarray[j] = temp;
i++;
j--;
}
}
//Recursion of the quicksort algorithm
if(l < j){
quickSort(qarray,l,j);
}
if(i < r){
quickSort(qarray,i,r);
}
}
int main(){
clock_t tStart = clock();
int myArray[26] ={4,2,5,6,1,3,17,14,67,45,32,66,88,
78,69,92,93,21,25,23,71,61,59,60,30,79};
for(int i=0;i < 26;i++){
cout << "Unsorted: " << myArray[i] << endl;
}quickSort(myArray,0,25);
for(int i=0;i < 26;i++){
cout << "Sorted: " << myArray[i] << endl;
}double seconds = clock() / double(CLK_TCK);
cout << "This program has been running for " << seconds << " seconds." << endl;
system("pause");
return 0;
}
Ошибка в этой строке (как минимум): int pivot = qarray[(l+r)]/2;
Должно быть int pivot = qarray[(l + r) / 2];
Нет смысла делить элемент массива на 2. Pivot — средний элемент диапазона, индекс которого (l + r) / 2
,
Других решений пока нет …