quicksort with random pivot

[FreeLemons]

umm. I am trying to convert some existing code I found that performed a quicksort on an array using leftmost element as pivot. I want to make the pivot selection random but I have run into logic errors for a long time. It seems to work sometimes now but not all the time so there is still something wrong and I don't know what. If someone could take a look and tell me where i went wrong I would appreaciate it. #include #include #include #include #define NUM_ITEMS 100 int numbers[NUM_ITEMS];// = {6,24,80,4,19,84,1,10,13,7}; void print(void); void quicksort(int beg, int end); void sort(int beg, int end); void swap(int left, int right); int pivot(int beg, int end); void selectsort(int left, int right); void main(void) { int i; //seed random number generator srand((unsigned)time( NULL )); //fill array with random integers for (i = 0; i < NUM_ITEMS; i++) numbers[i] = rand(); //perform quick sort on array quicksort(0, NUM_ITEMS); print(); exit(1); } void quicksort(int beg, int end) { sort(beg, end - 1); } void sort(int beg, int end) { int position; if (beg > end) return; if (beg == end) return; position = pivot(beg, end); sort(beg, position - 1); sort(position + 1, end); } int pivot(int beg, int end) { int left = beg, right = end, pivot; int rand_subscript; rand_subscript = (int) ((right-left) * rand() / (RAND_MAX + 1)) + left; pivot = numbers[rand_subscript]; while ((numbers[left] <= pivot) && (left < end)) { left++; } while (numbers[right] > pivot) { right--; } while (left < right) { swap(left, right); do { left++; }while ((numbers[left] <= pivot) && (left < end)); do { right--; }while (numbers[right] > pivot); if (right == rand_subscript) { rand_subscript = left; } } if ((numbers[right] != pivot) && (numbers[rand_subscript] == pivot)) swap(right, rand_subscript); print(); return right; } void swap(int left, int right) { int hold; hold = numbers[left]; numbers[left] = numbers[right]; numbers[right] = hold; } void selectsort(int left, int right) { int l = left, r = right; int ltemp, value, l_inc; for (l;l

[David Crow]

FreeLemons wrote: rand_subscript = (int) ((right-left) * rand() / (RAND_MAX + 1)) + left; I think this should be:

rand_subscript = (rand() % (right - left + 1)) + left;

---

"When I was born I was so surprised that I didn't talk for a year and a half." - Gracie Allen