nag_stable_sort (m01ctc) (PDF version)
m01 Chapter Contents
m01 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_stable_sort (m01ctc)


    1  Purpose
    7  Accuracy

1  Purpose

nag_stable_sort (m01ctc) rearranges a vector of arbitrary type objects into ascending or descending order.

2  Specification

#include <nag.h>
#include <nagm01.h>
void  nag_stable_sort (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_stable_sort (m01ctc) 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.
A stable sort is one which preserves the order of distinct data items that compare equal. This function uses nag_rank_sort (m01dsc), nag_make_indices (m01zac) and nag_reorder_vector (m01esc) in order to carry out a stable sort with the same specification as nag_quicksort (m01csc). nag_stable_sort (m01ctc) will be faster than nag_quicksort (m01csc) if the comparison function compare is slow or the data items are large. Internally a large amount of workspace may be required compared with nag_quicksort (m01csc).

4  References

Knuth D E (1973) The Art of Computer Programming (Volume 3) (2nd Edition) Addison–Wesley

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_stable_sort (m01ctc) 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.
On entry, stride=value.
Constraint: stridevalue.
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 time taken by nag_stable_sort (m01ctc) is approximately proportional to n logn .

10  Example

The example program reads a three column matrix of real numbers and sorts the first column into ascending order.

10.1  Program Text

Program Text (m01ctce.c)

10.2  Program Data

Program Data (m01ctce.d)

10.3  Program Results

Program Results (m01ctce.r)

nag_stable_sort (m01ctc) (PDF version)
m01 Chapter Contents
m01 Chapter Introduction
NAG Library Manual

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