     Search
Next: 0.3.1.6 References Up: 0.3.1 The Quicksort Previous: 0.3.1.4 Improvement Strategies

### 0.3.1.5 Source Code

Here is a full implementation of an unoptimized recursive Quicksort in C.

```/* ------------------------------------------------------------------------- */
/*   get_pivot - return the index of the selected pivot value
*/

int get_pivot (int low, int hi) {

/* safety net, this should not happen */
if (low == hi) return(data[low]);

/* return the greater of the first two items in the range  */
return( (data[low] > data[low+1]) ? low : (low+1) );
}

/* ------------------------------------------------------------------------- */
/*   swap - given two pointers to integers, swap their contents
*/

void swap (int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
num_swaps++;
}

/* ------------------------------------------------------------------------- */
/*   q_sort - Quicksort a data range
*/

void q_sort (int low, int hi) {
int pivot_index;                /* index in the data set of the pivot */
int pivot_value;                /* the value of the pivot element     */
int left, right;

/* select the pivot element and remember its value */
pivot_index = get_pivot(low, hi);
pivot_value = data[pivot_index];

/* do the partitioning */
left = low; right = hi;
do {

/* move left to the right bypassing elements already on the correct side */
while ((left <= hi) && (data[left] < pivot_value)) {
num_comps++;
left++;
}
num_comps++;

/* move right to the left bypassing elements already on the correct side */
while ((right >= low) && (pivot_value < data[right])) {
num_comps++;
right--;
}
num_comps++;

/*
*  if the pointers are in the correct order then they are pointing to two
*  items that are on the wrong side of the pivot value, swap them...
*/
if (left <= right) {
swap(&data[left], &data[right]);
left++;
right--;
}

} while (left <= right);

/* now recurse on both partitions as long as they are large enough */
if (low < right) q_sort(low, right);
if (left < hi) q_sort(left, hi);
}
```

Scott Gasch
1999-07-09