Sorting/PointerBased/pivotMedianOfMedians.c File Reference

Code to select median of medians as pivot index

Given array vals[left,right] select left as the pivot index. More...


Functions

int ascending (const void *, const void *)
 default ascending operator provided externally
int selectMedian (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Provided externally for selecting median as based on BFPRT algorithm.
int selectPivotIndex (void **vals, int left, int right)
 Code to select a pivot index around which to partition ar[left, right].


Detailed Description

Code to select median of medians as pivot index

Given array vals[left,right] select left as the pivot index.

Only works if a proper defaultComp is provided. This function is used as the default comparison between two elements in the array.

Author:
George Heineman
Date:
6/15/08

Function Documentation

int ascending ( const void *  ,
const void *   
)

default ascending operator provided externally

int selectMedian ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  left,
int  right 
)

Provided externally for selecting median as based on BFPRT algorithm.

The comparison function, cmp, is needed to compare elements.

Partition input array around the median of medians x. If kth largest is found, return absolute index; otherwise narrow to find kth smallest in A[left,pivotIndex-1] or (k-p)-th in A[pivotIndex+1,right].

int selectPivotIndex ( void **  vals,
int  left,
int  right 
)

Code to select a pivot index around which to partition ar[left, right].

Select median of medians.

Parameters:
vals the array of elements.
left the left end of the subarray range
right the right end of the subarray range
Returns:
int in the range [left, right] to use in partition.

Algorithm Development Kit 1.0