C++隨機快速排序錯誤

Question

我想實現快速排序算法，但不知何故我有一個錯誤，我只是不能fint它，我的randomizedPartition似乎工作正常。這是代碼。

#include <iostream> 
#include <cstdlib> 
#include <cmath> 

using namespace std; 

int randomizedPartition(int *v, int start, int end); 
void quickSort(int *v, int start, int end); 
void swap(int *p, int *q); 
void print(int *v, int len); 

int main(int argc, char const *argv[]) { 

    cout << "QUICK SORT:\n" << endl; 
    int v[]  = {6, 4, 7, 3, 0, 1 , 2, 9, 19}; 
    int len = sizeof(v)/sizeof(int); 

    cout << "Before Sorting: " << endl; 
    print(v, len); 
    cout << "After Sorting: " << endl; 
    quickSort(v, 0, len - 1); 
    print(v, len); 

    return 0; 
} 

int randomizedPartition(int *v, int start, int end) { 
    int len = (int) abs(end - start + 1); 
    srand (time(NULL)); 
    int idx  = rand() % len; 
    cout << "IDX RD: " << idx << endl; 
    int pivot = v[idx]; 
    swap(&v[start], &v[idx]); 

    int i = start - 1; 
    int j = start; 

    for (int posi = start + 1; posi <= end; ++posi) { 
     if(v[posi] <= pivot) { 
     ++i; 
     ++j; 
     swap(&v[posi], &v[i]); 
     swap(&v[posi], &v[j]); 
     } 
    } 

    cout << "Pivot: " << pivot << endl; 
    cout << "Pivot Index: " << (i + 1) << endl; 
    return ++i; 
} 

void quickSort(int *v, int start, int end) { 
    if (start < end) { 
     int idx = randomizedPartition(v, start, end); 
     print(v, end - start + 1); 
     cout << "Start: " << start << endl; 
     cout << "End: " << end << endl; 
     cout << "idx - 1: " << idx - 1 << endl; 
     cout << "idx + 1: " << idx + 1 << endl; 
     quickSort(v, start, idx - 1); 
     quickSort(v, idx + 1, end); 
    } 
} 

void print(int *v, int len) { 
    for (int i = 0; i < len; ++i) { 
    cout << *(v + i) << " "; 
    } 
    cout << "\n" << endl; 
} 

void swap(int *p, int *q) { 
    int temp = *p; 
    *p = *q; 
    *q = temp; 
} 

任何人都可以幫助我找到錯誤嗎？這是可能的輸出中的一個：

Before Sorting: 
6 4 7 3 0 1 2 9 19 

After Sorting: 
IDX RD: 2 
Pivot: 7 
Pivot Index: 6 
4 6 3 0 1 2 7 9 19 

Start: 0 
End: 8 
idx - 1: 5 
idx + 1: 7 
IDX RD: 5 
Pivot: 2 
Pivot Index: 2 
0 1 2 6 3 4 

Start: 0 
End: 5 
idx - 1: 1 
idx + 1: 3 
IDX RD: 1 
Pivot: 1 
Pivot Index: 1 
0 1 

Start: 0 
End: 1 
idx - 1: 0 
idx + 1: 2 
IDX RD: 2 
Pivot: 2 
Pivot Index: 3 
0 1 6 

Start: 3 
End: 5 
idx - 1: 2 
idx + 1: 4 
IDX RD: 1 
Pivot: 1 
Pivot Index: 4 
0 3 

Start: 4 
End: 5 
idx - 1: 3 
idx + 1: 5 
IDX RD: 1 
Pivot: 3 
Pivot Index: 7 
0 9 

Start: 7 
End: 8 
idx - 1: 6 
idx + 1: 8 
0 9 6 2 1 4 7 3 19 

Answer 1

你在randomizedPartition指數應start + rand() % len，不只是rand() % len。

另外，作爲一個附註，你的print函數實際上並沒有做你想要的。您希望它打印元素start到end，但它實際上是打印0到end - start。一般情況下，您的調試過程和您的編碼過程會從試圖保持乾淨和簡單的事情中受益。這段代碼現在有點亂，這使得它更難調試。