Defines | |
#define | SWAP(a, p1, p2, type) |
Macro to swap two elements in the array. | |
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 | medianOfFour (void **ar, int left, int gap, int(*cmp)(const void *, const void *)) |
determine median of four elements in array ar[left], ar[left+gap], ar[left+gap*2], ar[left+gap*3] and ensure that ar[left+gap*2] contains this median value once done. | |
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. |
#define SWAP | ( | a, | |||
p1, | |||||
p2, | |||||
type | ) |
Value:
{ \ type _tmp__ = a[p1]; \ a[p1] = a[p2]; \ a[p2] = _tmp__; \ }
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 void medianOfFour | ( | void ** | ar, | |
int | left, | |||
int | gap, | |||
int(*)(const void *, const void *) | cmp | |||
) | [static] |
determine median of four elements in array ar[left], ar[left+gap], ar[left+gap*2], ar[left+gap*3] and ensure that ar[left+gap*2] contains this median value once done.
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.
Goal is to consider groups of size b. In this code, b=4. In the original BFPRT algorithm, b=5.
1. Divide the elements into floor(n/b) groups of b elements and find median value of each of these groups. Consider this set of all medians to be the set M.
2. If |M| > b, then recursively apply until <=b groups are left
3. In the base case of the recursion, simply use INSERTION SORT to sort remaining <=b median values and choose the median of this sorted set.
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