nag_quicksort (m01csc) (PDF version)
m01 Chapter Contents
m01 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_quicksort (m01csc)


    1  Purpose
    7  Accuracy

1  Purpose

nag_quicksort (m01csc) rearranges a vector of arbitrary type objects into ascending or descending order.

2  Specification

#include <nag.h>
#include <nagm01.h>
void  nag_quicksort (Pointer vec, size_t n, size_t size, ptrdiff_t stride,
Integer (*compare)(const Nag_Pointer a, const Nag_Pointer b),
Nag_SortOrder order, NagError *fail)

3  Description

nag_quicksort (m01csc) sorts a set of n  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: n0 .
3:     size size_tInput
On entry: the size of each object to be sorted.
Constraint: size1 .
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 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 or Nag_Descending.
7:     fail NagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

On entry, stride = value while size=value . These arguments must satisfy stride size .
Dynamic memory allocation failed.
On entry, argument order had an illegal value.
On entry, n=value.
Constraint: nvalue.
On entry, size=value.
Constraint: sizevalue.
These arguments are limited to an implementation-dependent size which is printed in the error message.
On entry, n=value.
Constraint: n0.
On entry, size=value.
Constraint: size1.
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 logn . 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.

10.1  Program Text

Program Text (m01csce.c)

10.2  Program Data

Program Data (m01csce.d)

10.3  Program Results

Program Results (m01csce.r)

nag_quicksort (m01csc) (PDF version)
m01 Chapter Contents
m01 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2015