PJ_ PJ_ - 1 month ago 21
C++ Question

C++ Randomized Quick Sort Bug

I'm trying to implement the quick sort algorithm but somehow Im having a bug and I just can't fint it, my randomizedPartition seems to be working fine. Here is the code.

#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;
}


Can anyone help me to finde the bug ? Here is one of the possible outputs:

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

Your index in randomizedPartition should be start + rand() % len, not just rand() % len.

Also, as a side note, your print function isn't actually doing what you want it to. You want it to print the elements start through end, but it's actually printing 0 through end - start. Your debugging process and your coding process in general would benefit from trying to keep things clean and simple. The code is a bit of a mess right now which makes it harder to debug.