Functions | |
int | partition (void **ar, int(*cmp)(const void *, const void *), int left, int right, int idx) |
Partition ar[left, right] around the value stored in ar[idx]. | |
static void | _insertion (void **ar, int(*cmp)(const void *, const void *), int low, int right, int gap) |
specialized insertion sort up to five elements with spaced gap. | |
static int | medianOfMedians (void **ar, int(*cmp)(const void *, const void *), int left, int right, int gap) |
Find suitable pivotIndex to use for ar[left,right] with closed bound on both sides. | |
int | selectMedian (void **ar, int(*cmp)(const void *, const void *), int left, int right) |
Provided externally for selecting median as based on BFPRT algorithm. |
static void _insertion | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | low, | |||
int | right, | |||
int | gap | |||
) | [static] |
specialized insertion sort up to five elements with spaced gap.
static int medianOfMedians | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | left, | |||
int | right, | |||
int | gap | |||
) | [static] |
Find suitable pivotIndex to use for ar[left,right] with closed bound on both sides.
1. Divide the elements into floor(n/4) groups of 4 elements and use _insertion on each group 2. Pick median from each sorted groups (3rd element). 3. Use select recursively to find median x of floor(n/4) medians found in step 2. This is known as the median-of-medians.
int partition | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | left, | |||
int | right, | |||
int | pivotIndex | |||
) |
Partition ar[left, right] around the value stored in ar[idx].
ar | contents of array | |
cmp | comparison function | |
left | lower bound index position (inclusive) | |
right | upper bound index position (inclusive) | |
pivotIndex | index around which the partition is being made. |
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].
Algorithm Development Kit 1.0