Contains Median Sort implementation. More...
#include "report.h"
Functions | |
int | selectKth (void **vals, int(*cmp)(const void *, const void *), int k, int left, int right) |
Externally provided method to select Kth element from subarray. | |
int | selectMedian (void **ar, int(*cmp)(const void *, const void *), int left, int right) |
Code to select median is externally provided. | |
int | partition (void **ar, int(*cmp)(const void *, const void *), int left, int right, int pivotIndex) |
Partition ar[left, right] around the value stored in ar[idx]. | |
void | mediansort (void **ar, int(*cmp)(const void *, const void *), int left, int right) |
Sort using mediansort method. | |
void | sortPointers (void **vals, int n, int(*cmp)(const void *, const void *)) |
Apply median sort. |
Contains Median Sort implementation.
If compiled with -DMEDIAN set, then this relies on a selectMedian externally provided function to select the median; otherwise, it falls back on using an externally provided selectKth.
void mediansort | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | left, | |||
int | right | |||
) |
Sort using mediansort method.
ar | array of elements to be sorted. | |
cmp | comparison function to order elements. | |
left | The left-bounds within which to sort (0 <= left < ar.length) | |
right | The right-bounds within which to sort (0 <= right < ar.length) |
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 selectKth | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | k, | |||
int | left, | |||
int | right | |||
) |
Externally provided method to select Kth element from subarray.
Note 1 <= k <= right-left+1. The comparison function, cmp, is needed to properly compare elements. Worst-case is quadratic, O(n^2).
int selectMedian | ( | void ** | ar, | |
int(*)(const void *, const void *) | cmp, | |||
int | left, | |||
int | right | |||
) |
Code to select median is externally provided.
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].
void sortPointers | ( | void ** | vals, | |
int | n, | |||
int(*)(const void *, const void *) | cmp | |||
) |
Apply median sort.
Algorithm Development Kit 1.0