Search

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