hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_sort_arbitrary_rank (m01dz)

Purpose

nag_sort_arbitrary_rank (m01dz) ranks arbitrary data according to a user-supplied comparison function.

Syntax

[irank, ifail] = m01dz(compar, m1, m2)
[irank, ifail] = nag_sort_arbitrary_rank(compar, m1, m2)

Description

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 1010.

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
The result of the function.
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 < m1m20<m1m2.

Optional Input Parameters

None.

Input Parameters Omitted from the MATLAB Interface

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 ii is first in the rank ordering, irank(i)iranki contains m1.
2:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry,m2 < 1m2<1,
orm1 < 1m1<1,
orm1 > m2m1>m2.

Accuracy

Not applicable.

Further Comments

The average time taken by the function is approximately proportional to n × log(n)n×log(n), where n = m2m1 + 1n=m2-m1+1; it will usually be dominated by the time taken in compar.

Example

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

function [result] = compar(i,j)
  iv = [int64(2), 1, -1, 0, 2, -2, 0, 1, 1, -1, 1, 2];

  rv = [3.0, 4.0, 6.0, 5.0, 2.0, 7.0, 4.0, 3.0, 5.0, 2.0, 0.0, 1.0];

  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
 

irank =

                   12
                    8
                    2
                    5
                   11
                    1
                    4
                    7
                    9
                    3
                    6
                   10


ifail =

                    0


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

function [result] = compar(i,j)
  iv = [int64(2), 1, -1, 0, 2, -2, 0, 1, 1, -1, 1, 2];

  rv = [3.0, 4.0, 6.0, 5.0, 2.0, 7.0, 4.0, 3.0, 5.0, 2.0, 0.0, 1.0];

  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
 

irank =

                   12
                    8
                    2
                    5
                   11
                    1
                    4
                    7
                    9
                    3
                    6
                   10


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013