NAG CL Interface
m01dsc (rank_​sort)

1 Purpose

m01dsc ranks a vector of arbitrary data type objects in ascending or descending order.

2 Specification

#include <nag.h>
void  m01dsc (const Pointer vec, size_t n, ptrdiff_t stride,
Integer (*compare)(const Nag_Pointer a, const Nag_Pointer b),
Nag_SortOrder order, size_t ranks[], NagError *fail)
The function may be called by the names: m01dsc, nag_sort_rank_sort or nag_rank_sort.

3 Description

m01dsc ranks a set of n data objects of arbitrary type, which are stored in the elements of an array at intervals of length stride. The ranks are in the range 0 to n-1 .
Either ascending or descending ranking order may be specified.
m01dsc uses a variant of list merging as described by Knuth (1973).

4 References

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

5 Arguments

1: vec[n] const Pointer  Input
On entry: the array of objects to be ranked.
2: n size_t Input
On entry: the number n of objects.
Constraint: 0nMAX_LENGTH, where MAX_LENGTH is an implementation-dependent value for the maximum size of an array.
3: stride ptrdiff_t Input
On entry: the increment between data items in vec to be ranked.
Note: if stride is positive, vec should point at the first data object; otherwise vec should point at the last data object.
Constraint: 0<stridep, where p is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
4: compare function, supplied by the user External Function
m01dsc 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.
5: order Nag_SortOrder Input
On entry: specifies whether the array is to be ranked into ascending or descending order.
Constraint: order=Nag_Ascending or Nag_Descending.
6: ranks[n] size_t Output
On exit: the ranks of the corresponding data elements in vec.
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_BAD_PARAM
On entry, argument order had an illegal value.
NE_INT_ARG_EQ
On entry, stride=value.
Constraint: stride0.
NE_INT_ARG_GT
On entry, n=value.
Constraint: nvalue, 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.

7 Accuracy

Not applicable.

8 Parallelism and Performance

m01dsc is not threaded in any implementation.

9 Further Comments

The time taken by m01dsc is approximately proportional to n logn .

10 Example

The example program reads a list of real numbers and ranks them into ascending order.

10.1 Program Text

Program Text (m01dsce.c)

10.2 Program Data

Program Data (m01dsce.d)

10.3 Program Results

Program Results (m01dsce.r)