# Randomized Quicksort problem

• 04-06-2012
Grigoris Savvas
Randomized Quicksort problem
I am trying to make a randomized quicksort. I have try a lot of quicksorts varieties to see if i can work on others but still i cannot make it to run properly. My quicksort sorts an array of structs based on an id. It is the same (i think) like an ordinary array, except from the refference to the struct. The code is based on a standar quicksort code that works with the left element of the array as pivot and i just swap the randomized pivot element with the left, so it will work just the same. But sometimes the results are correct and others are wrong.

Code:

``` typedef struct Student{     int id;                char name[20];        char surname[20]; } Student; typedef struct Students{    Student *arr;     int size;                int sorted; //1 if by surname, name, 2 if by ID } Students; void sortID(Students *st){     quickSort(st->arr,0 , st->size-1);     st->sorted = 2; }     int pivotSelect(int left, int right){         srand(time(NULL));     int pivot = left + rand()%(right-left + 1);     return pivot; }     int partition (Student *A, int left, int right, int pivotIndex){     swap(&A[left],&A[pivotIndex]);         int lc = left + 1;     int rc = right;     while (lc < rc) {           while ( A[lc].id<=A[left].id  && lc<right)                 lc++;           while (A[rc].id>A[left].id)                 rc--;           if (lc < rc)                 swap(&A[lc], &A[rc]);     }     swap (&A[left], &A[rc]);     return rc; } void quickSort(Student *A, int left, int right) {     if (left >= right) return;     int pivotIndex = pivotSelect(left,right);     int p = partition(A, idCmp, left, right, pivotIndex);     quickSort(A, left, p-1);     quickSort(A, p+1, right); }```
• 04-06-2012
laserlight
Does your code always work when you change pivotSelect to just return left?

By the way, you should move the srand call to near the start of your main function. There is no point seeding the PRNG for each time you want to call rand.
• 04-06-2012
iMalc
I'd word it a bit more strongly than that... calling srand(time(NULL)) more than once in your program is a bug. Re-seeding like that destroys the randomness. Why? Largely because whilst the absolute time that your program starts executing is fairly random, the relative time differences whilst your program is running are fairly predictable.
Move that line to the top of main.

Next, a good way to solve the problem is to find the simplest possible case that does not work, then debug that case.
First, check does it work correctly for zero items?
Does it work correctly for one item?
Does it work correctly for two items already in order?
Does it work correctly for two items out of order?
Does it work for three items in any order?