NAG Library Function Document

nag_quicksort (m01csc)

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.

4 References

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

5 Arguments

1: vec[ $n$ ] – Pointer Input/Output

On entry: the array of objects to be sorted.

On exit: the objects rearranged into sorted order.

2: n – size_tInput

On entry: the number,

n

, of objects to be sorted.

Constraint:

n \geq 0

3: size – size_tInput

On entry: the size of each object to be sorted.

Constraint:

size \geq 1

4: stride – ptrdiff_tInput

On entry: the increment between data items in vec to be sorted.

Note: if stride is positive, vec should point at the first data object; otherwise vec should point at the last data object.

Constraint:

|stride| \geq size

5: 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:

$- 1$	if the first data field is less than the second,
$0$	if the first data field is equal to the second,
$1$	if the first data field is greater than the second.

The specification of compare is:

Integer

compare (const Nag_Pointer a, const Nag_Pointer b)

1: a – const Nag_Pointer Input: On entry: the first data field.
2: b – const Nag_Pointer Input: On entry: the second data field.

6: order – Nag_SortOrderInput

On entry: specifies whether the array is to be sorted into ascending or descending order.

Constraint:

order = Nag_Ascending

Nag_Descending

7: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_2_INT_ARG_LT: On entry, $|stride| = ⟨value⟩$ while $size = ⟨value⟩$ . These arguments must satisfy $|stride| \geq size$ .
NE_ALLOC_FAIL: Dynamic memory allocation failed.
NE_BAD_PARAM: On entry, argument order had an illegal value.
NE_INT_ARG_GT: On entry, $n = ⟨value⟩$ .
Constraint: $n \leq ⟨value⟩$ .
On entry, $size = ⟨value⟩$ .
Constraint: $size \leq ⟨value⟩$ .
These arguments are limited to an implementation-dependent size which is printed in the error message.
NE_INT_ARG_LT: On entry, $n = ⟨value⟩$ .
Constraint: $n \geq 0$ .
On entry, $size = ⟨value⟩$ .
Constraint: $size \geq 1$ .
The absolute value of stride must not be less than size.

7 Accuracy

Not applicable.

8 Parallelism and Performance

Not applicable.

9 Further Comments

The average time taken by the function is approximately proportional to

n \log (n)

. The worst case time is proportional to

n^{2}

but this is extremely unlikely to occur.

10 Example

The example program reads a two-dimensional array of numbers and sorts the second column into ascending order.

NAG Library Function Documentnag_quicksort (m01csc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Document

nag_quicksort (m01csc)