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