Contains Median Sort implementation that switches to Insertion Sort when the problem size is small enough. More...
#include "report.h"
Functions | |
| int | selectKth (void **ar, int(*cmp)(const void *, const void *), int k, int left, int right) |
| Externally provided method to select Kth element from subarray. | |
| 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 | insertion (void **ar, int(*cmp)(const void *, const void *), int low, int high) |
| Perform insertion sort over the given subarray. | |
| void | selectionSort (void **ar, int(*cmp)(const void *, const void *), int low, int high) |
| By contrast, perform Selection Sort over subarray. | |
| void | mediansort (void **ar, int(*cmp)(const void *, const void *), int left, int right) |
| Sort using medianSort method. | |
| void | sortPointers (void **vals, int total_elems, int(*cmp)(const void *, const void *)) |
| Sort the pointers via median sort. | |
Variables | |
| int | minSize |
| Minimum size beyond which to use Insertion Sort. | |
Contains Median Sort implementation that switches to Insertion Sort when the problem size is small enough.
| void insertion | ( | void ** | ar, | |
| int(*)(const void *, const void *) | cmp, | |||
| int | low, | |||
| int | high | |||
| ) |
Perform insertion sort over the given subarray.
| 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 | array of elements to be sorted. | |
| cmp | comparison function to order elements. | |
| left | lower bound index position (inclusive) | |
| right | upper bound index position (exclusive) | |
| pivotIndex | index around which the partition is being made. |
| void selectionSort | ( | void ** | ar, | |
| int(*)(const void *, const void *) | cmp, | |||
| int | low, | |||
| int | high | |||
| ) |
By contrast, perform Selection Sort over subarray.
| 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).
| void sortPointers | ( | void ** | vals, | |
| int | total_elems, | |||
| int(*)(const void *, const void *) | cmp | |||
| ) |
Sort the pointers via median sort.
| int minSize |
Minimum size beyond which to use Insertion Sort.
Algorithm Development Kit 1.0