Search

0.3.10.3 Source Code

/* ------------------------------------------------------------------------- */
/*   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
 */

int nth_largets_q_sort (int nth, 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;

  if (low == hi) return(data[low]);

  /* 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);

  if ((right - low) > nth) nth_largest_q_sort(nth, low, right);
    else nth_largets_q_sort((nth - left), left, hi);

}