Search
Next: 0.4 Graph Algorithms Up: 0.3.10 The nth Largest Previous: 0.3.10.2 Modified Quicksort

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

}
```

Scott Gasch
1999-07-09