C++ランダム化されたクイックソートバグ

Question

クイックソートアルゴリズムを実装しようとしていますが、どういうわけかバグがありました。私はそれに気づくことができません。私の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まで印刷しています。あなたのデバッグプロセスとコーディングプロセスは、一般的にクリーンでシンプルなものを保つことによって利益を得ます。コードはちょっと混乱しており、デバッグが難しくなっています。