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