SORT - Functions to sort arrays of data or arrays of indices
hpsort sort an array of floats by the heap sort method
qkisort sort an array of indices i[] so that
a[i[0]] <= a[i[1]] <= ... <= a[i[n-1]]
uses the "quick sort" method
qkifind partially sort an array of indices i[] so that the
index i[m] has the value it would have if the entire
array of indices were sorted such that
a[i[0]] <= a[i[1]] <= ... <= a[i[n-1]]
uses the "quick sort" method
qksort sort an array of floats such that a[0] <= a[1] <= ... <= a[n-1]
uses the "quick sort" method
qkfind partially sort an array of floats so that the element a[m] has
the value it would have if the entire array were sorted
such that a[0] <= a[1] <= ... <= a[n-1]
uses the "quick sort" method
Function Prototypes:
void hpsort (int n, float a[]);
void qkisort (int n, float a[], int i[]);
void qkifind (int m, int n, float a[], int i[]);
void qksort (int n, float a[]);
void qkfind (int m, int n, float a[]);
hpsort:
Input:
n number of elements in a
a array[n] to be sorted
Output:
a array[n] sorted
qkisort:
Input:
n number of elements in array a
a array[n] elements
i array[n] indices to be sorted
Output:
i array[n] indices sorted
qkifind:
Input:
m index of element to be found
n number of elements in array a
a array[n] elements
i array[n] indices to be partially sorted
Output:
i array[n] indices partially sorted sorted
qksort:
Input:
n number of elements in array a
a array[n] containing elements to be sorted
Output:
a array[n] containing sorted elements
qkfind:
Input:
m index of element to be found
n number of elements in array a
a array[n] to be partially sorted
Output:
a array[n] partially sorted
Notes:
hpsort:
The heap sort algorithm is, at worst, N log_2 N, and in most cases
is 20% faster. Adapted from Standish.
qkisort, qkifind, qksort, qkfind:
n must be less than 2^NSTACK, where NSTACK is defined above.
qkisort:
This function is adapted from procedure quicksort by
Hoare, C.A.R., 1961, Communications of the ACM, v. 4, p. 321;
the main difference is that recursion is accomplished
explicitly via a stack array for efficiency; also, a simple
insertion sort is used to sort subarrays too small to be
partitioned efficiently.
qkifind:
This function is adapted from procedure find by
Hoare, C.A.R., 1961, Communications of the ACM, v. 4, p. 321.
qksort:
This function is adapted from procedure quicksort by
Hoare, C.A.R., 1961, Communications of the ACM, v. 4, p. 321;
the main difference is that recursion is accomplished
explicitly via a stack array for efficiency; also, a simple
insertion sort is used to sort subarrays too small to be
partitioned efficiently.
qkfind:
This function is adapted from procedure find by Hoare 1961.
Reference:
hpsort:
Standish, T. A., Data Structure Techniques, p. 91.
See also Press, W. A., et al., Numerical Recipes in C.
quick sort:
Hoare, C.A.R., 1961, Communications of the ACM, v. 4, p. 321.
Author: Dave Hale, Colorado School of Mines, 12/26/89