A non-recursive implementation to select the kth smallest element from the subarray ar[left, right]. More...
Functions | |
int | selectPivotIndex (void **vals, int left, int right) |
Code to select a pivot index around which to partition ar[left, right]. | |
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]. | |
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. |
A non-recursive implementation to select the kth smallest element from the subarray ar[left, right].
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.
ar | array of elements to be sorted. | |
cmp | comparison function to order elements. | |
k | kth smallest element to select. | |
left | lower bound index position (inclusive) | |
right | upper bound index position (inclusive) |
int selectPivotIndex | ( | void ** | vals, | |
int | left, | |||
int | right | |||
) |
Code to select a pivot index around which to partition ar[left, right].
Select a random index from [left,right].
vals | the array of elements. | |
left | the left end of the subarray range | |
right | the right end of the subarray range |
This really needs to have the comparison method passed in! But I don't want to change the interface, so this will suffice in the short term since all we have are strings in the example.
Algorithm Development Kit 1.0