NAG CL Interface
m01csc (quicksort)

Settings help

CL Name Style:


1 Purpose

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

2 Specification

#include <nag.h>
void  m01csc (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)
The function may be called by the names: m01csc, nag_sort_quicksort or nag_quicksort.

3 Description

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.
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_t Input
On entry: the number, n , of objects to be sorted.
Constraint: 0nMAX_LENGTH, where MAX_LENGTH is an implementation-dependent value for the maximum size of an array.
3: size size_t Input
On entry: the size of each object to be sorted.
Constraint: 1sizep, where p is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
4: stride ptrdiff_t Input
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: size|stride|p, where p is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
5: compare function, supplied by the user External Function
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_SortOrder Input
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 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_2_INT_ARG_LT
On entry, |stride| = value while size=value . These arguments must satisfy |stride| 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, |stride|=value.
Constraint: |stride|value, an implementation-dependent size that is printed in the error message.
On entry, n=value.
Constraint: nvalue, an implementation-dependent size that is printed in the error message.
On entry, size=value.
Constraint: sizevalue, an implementation-dependent size that is printed in the error message.
NE_INT_ARG_LT
On entry, n=value.
Constraint: n0.
On entry, size=value.
Constraint: size1.

7 Accuracy

Not applicable.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.
m01csc is not threaded in any implementation.

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.

10.1 Program Text

Program Text (m01csce.c)

10.2 Program Data

Program Data (m01csce.d)

10.3 Program Results

Program Results (m01csce.r)