nag_sort_arbitrary_rank (m01dz) is a general purpose function for ranking arbitrary data. nag_sort_arbitrary_rank (m01dz) does not access the data directly; instead it calls compar to determine the relative ordering of any two data items. The data items are identified simply by an integer in the range m1 to m2.

nag_sort_arbitrary_rank (m01dz) uses a variant of list-merging, as described on pages 165–166 in Knuth (1973). The function takes advantage of natural ordering in the data, and uses a simple list insertion in a preparatory pass to generate ordered lists of length at least

10

References

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

Parameters

Compulsory Input Parameters

1: $compar$ – function handle or string containing name of m-file

compar must specify the relative ordering of any two data items; it must return true if item ii must come strictly after item j in the rank ordering.

[result] = compar(ii, j)

Input Parameters

1: $ii$ – int64int32nag_int scalar
2: $j$ – int64int32nag_int scalar: ii and j identify the data items to be compared.

Output Parameters

1: $result$ – logical scalar: result must be true if item ii must come strictly after item j in the rank ordering.

2: $m1$ – int64int32nag_int scalar

3: $m2$ – int64int32nag_int scalar

m1 and m2 must specify the range of data items to be ranked, and the range of ranks to be assigned. Specifically, nag_sort_arbitrary_rank (m01dz) ranks the data items identified by integers in the range m1 to m2, and assigns ranks in the range m1 to m2 which are stored in elements m1 to m2 of irank.

Constraint:

0 < m1 \leq m2

Optional Input Parameters

None.

Output Parameters

1: $irank (m2)$ – int64int32nag_int array: Elements m1 to m2 of irank contain the ranks of the data items m1 to m2. Note that the ranks are in the range m1 to m2: thus, if item $i$ is first in the rank ordering, $irank (i)$ contains m1.
2: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$

On entry,	$m2 < 1$ ,
or	$m1 < 1$ ,
or	$m1 > m2$ .

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

Not applicable.

Further Comments

The average time taken by the function is approximately proportional to

n \times \log (n)

, where

n = m2 - m1 + 1

; it will usually be dominated by the time taken in compar.

Example

This example reads records, each of which contains an integer key and a double number. The program ranks the records first of all in ascending order of the integer key; records with equal keys are ranked in descending order of the double number if the key is negative, in ascending order of the double number if the key is positive, and in their original order if the key is zero. After calling nag_sort_arbitrary_rank (m01dz), the program calls nag_sort_permute_invert (m01za) to convert the ranks to indices, and prints the records in rank order.

Open in the MATLAB editor: m01dz_example

function m01dz_example


fprintf('m01dz example results\n\n');

global iv rv;

iv = [int64(2), 1, -1, 0, 2, -2, 0, 1, 1, -1, 1, 2];
rv = [        3,  4,  6, 5, 2,  7, 4, 3, 5,  2, 0, 1];

m1 = int64(1);
m2 = int64(12);
[irank, ifail] = m01dz(@compar, m1, m2);

[irank, ifail] = m01za(irank, m1);

fprintf('Data in sorted order\n\n');
for i = m1:m2
  fprintf('%7d%7.1f\n',iv(irank(i)),rv(irank(i)));
end



function [result] = compar(i,j)

  global iv rv;

  if (iv(i) ~= iv(j))
    result = iv(i) > iv(j);
  elseif (iv(i) < 0)
    result = rv(i) < rv(j);
  elseif (iv(i) > 0)
    result = rv(i) > rv(j);
  else
    result = i<j;
  end

m01dz example results

Data in sorted order

     -2    7.0
     -1    6.0
     -1    2.0
      0    4.0
      0    5.0
      1    0.0
      1    3.0
      1    4.0
      1    5.0
      2    1.0
      2    2.0
      2    3.0

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox