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

NAG Library Function Document

nag_stable_sort (m01ctc)

+ Contents

    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:     nsize_tInput
On entry: the number n  of objects to be sorted.
Constraint: n0 .
3:     sizesize_tInput
On entry: the size of each object to be sorted.
Constraint: size1 .
4:     strideptrdiff_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:     comparefunction, 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:     aconst Nag_Pointer Input
On entry: the first data field.
2:     bconst Nag_Pointer Input
On entry: the second data field.
6:     orderNag_SortOrderInput
On entry: specifies whether the array is to be sorted into ascending or descending order.
Constraint: order=Nag_Ascending or Nag_Descending.
7:     failNagError *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 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: 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.
NE_INT_ARG_LT
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  Further Comments

The time taken by nag_stable_sort (m01ctc) is approximately proportional to n logn .

9  Example

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

9.1  Program Text

Program Text (m01ctce.c)

9.2  Program Data

Program Data (m01ctce.d)

9.3  Program Results

Program Results (m01ctce.r)


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

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