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:     n size_tInput
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_tInput
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_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: sizestridep, 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 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.7 in How to Use the NAG Library and its Documentation).

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, 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.
On entry, stride=value.
Constraint: stridevalue, 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

nag_stable_sort (m01ctc) is not threaded in any implementation.

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)

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