sort.cwp.lib

su 的源代码库

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