NAG Library Function Document
nag_quicksort (m01csc) rearranges a vector of arbitrary type objects into ascending or descending order.
||nag_quicksort (Pointer vec,
(*compare)(const Nag_Pointer a,
const Nag_Pointer b),
nag_quicksort (m01csc) sorts a set of
data objects of arbitrary type, which are stored in the elements of an array at intervals of length stride
. The function may be used to sort a column of a two-dimensional array. Either ascending or descending sort order may be specified.
nag_quicksort (m01csc) is based on Singleton's implementation of the ‘median-of-three’ Quicksort algorithm, Singleton (1969)
, but with two additional modifications. First, small subfiles are sorted by an insertion sort on a separate final pass, Sedgewick (1978)
. Second, if a subfile is partitioned into two very unbalanced subfiles, the larger of them is flagged for special treatment: before it is partitioned, its end-points are swapped with two random points within it; this makes the worst case behaviour extremely unlikely.
Maclaren N M (1985) Comput. J. 28 448
Sedgewick R (1978) Implementing Quicksort programs Comm. ACM 21 847–857
Singleton R C (1969) An efficient algorithm for sorting with minimal storage: Algorithm 347 Comm. ACM 12 185–187
vec – Pointer Input/Output
On entry: the array of objects to be sorted.
On exit: the objects rearranged into sorted order.
n – size_tInput
the number, , of objects to be sorted.
size – size_tInput
On entry: the size of each object to be sorted.
stride – ptrdiff_tInput
: the increment between data items in vec
to be sorted.
is positive, vec
should point at the first data object; otherwise vec
should point at the last data object.
compare – function, supplied by the userExternal Function
nag_quicksort (m01csc) compares two data objects. If its arguments are pointers to a structure, this function must allow for the offset of the data field in the structure (if it is not the first).
The function must return:
|if the first data field is less than the second,|
|if the first data field is equal to the second,|
|if the first data field is greater than the second.|
The specification of compare
compare (const Nag_Pointer a,
const Nag_Pointer b)
a – const Nag_Pointer Input
On entry: the first data field.
b – const Nag_Pointer Input
On entry: the second data field.
order – Nag_SortOrderInput
On entry: specifies whether the array is to be sorted into ascending or descending order.
fail – NagError *Input/Output
The NAG error argument (see Section 3.6
in the Essential Introduction).
6 Error Indicators and Warnings
On entry, while . These arguments must satisfy .
Dynamic memory allocation failed.
On entry, argument order
had an illegal value.
On entry, .
On entry, .
These arguments are limited to an implementation-dependent size which is printed in the error message.
On entry, .
The absolute value of stride
must not be less than size
The average time taken by the function is approximately proportional to . The worst case time is proportional to but this is extremely unlikely to occur.
The example program reads a two-dimensional array of numbers and sorts the second column into ascending order.
9.1 Program Text
Program Text (m01csce.c)
9.2 Program Data
Program Data (m01csce.d)
9.3 Program Results
Program Results (m01csce.r)