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_charvec_sort (m01cc)

Purpose

nag_sort_charvec_sort (m01cc) rearranges a vector of character data so that a specified substring is in ASCII or reverse ASCII order.

Syntax

[ch, ifail] = m01cc(ch, m1, l1, l2, order, 'm2', m2)
[ch, ifail] = nag_sort_charvec_sort(ch, m1, l1, l2, order, 'm2', m2)

Description

nag_sort_charvec_sort (m01cc) is based on Singleton's implementation of the ‘median-of-three’ Quicksort algorithm (see Singleton (1969)), but with two additional modifications. First, small subfiles are sorted by an insertion sort on a separate final pass (see Sedgewick (1978)) Second, if a subfile is partitioned into two very unbalanced subfiles, the larger of them is flagged for special treatment: before it is partitioned, its end points are swapped with two random points within it; this makes the worst case behaviour extremely unlikely.
Only the substring (l1:l2) of each element of the array ch is used to determine the sorted order, but the entire elements are rearranged into sorted order.

References

Sedgewick R (1978) Implementing Quicksort programs Comm. ACM 21 847–857
Singleton R C (1969) An efficient algorithm for sorting with minimal storage: Algorithm 347 Comm. ACM 12 185–187

Parameters

Compulsory Input Parameters

1:     ch(m2) – cell array of strings
m2, the dimension of the array, must satisfy the constraint m2m1m2m1.
Elements m1 to m2 of ch must contain character data to be sorted.
Constraint: the length of each element of ch must not exceed 255255.
2:     m1 – int64int32nag_int scalar
The index of the first element of ch to be sorted.
Constraint: m1 > 0m1>0.
3:     l1 – int64int32nag_int scalar
4:     l2 – int64int32nag_int scalar
Only the substring (l1:l2) of each element of ch is to be used in determining the sorted order.
Constraint: 0 < l1l2LEN(ch(1))0<l1l2LEN(ch1).
5:     order – string (length ≥ 1)
If order = 'A'order='A', the values will be sorted into ASCII order.
If order = 'R'order='R', into reverse ASCII order.
Constraint: order = 'A'order='A' or 'R''R'.

Optional Input Parameters

1:     m2 – int64int32nag_int scalar
Default: The dimension of the array ch.
The index of the last element of ch to be sorted.
Constraint: m2m1m2m1.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     ch(m2) – cell array of strings
These values are rearranged into sorted order.
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,
orl2 < 1l2<1,
orl1 < 1l1<1,
orl1 > l2l1>l2,
orl2 > LEN(ch(1))l2>LEN(ch1).
  ifail = 2ifail=2
On entry,order is not 'A' or 'R'.
  ifail = 3ifail=3
On entry,the length of each element of ch exceeds 255255.

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. The worst case time is proportional to n2n2, but this is extremely unlikely to occur.
The function relies on the Fortran intrinsic functions LLT and LGT to order characters according to the ASCII collating sequence.

Example

function nag_sort_charvec_sort_example
ch = {'A02AAF   289';
      'A02ABF   523';
      'A02ACF   531';
      'C02ADF   169';
      'C02AEF   599';
      'C05ADF  1351';
      'C05AGF   240';
      'C05AJF   136';
      'C05AVF   211';
      'C05AXF   183';
      'C05AZF  2181'};
m1 = int64(1);
l1 = int64(7);
l2 = int64(12);
order = 'Reverse ASCII';
[chOut, ifail] = nag_sort_charvec_sort(ch, m1, l1, l2, order)
 

chOut = 

    'C05AZF  2181'
    'C05ADF  1351'
    'C02AEF   599'
    'A02ACF   531'
    'A02ABF   523'
    'A02AAF   289'
    'C05AGF   240'
    'C05AVF   211'
    'C05AXF   183'
    'C02ADF   169'
    'C05AJF   136'


ifail =

                    0


function m01cc_example
ch = {'A02AAF   289';
      'A02ABF   523';
      'A02ACF   531';
      'C02ADF   169';
      'C02AEF   599';
      'C05ADF  1351';
      'C05AGF   240';
      'C05AJF   136';
      'C05AVF   211';
      'C05AXF   183';
      'C05AZF  2181'};
m1 = int64(1);
l1 = int64(7);
l2 = int64(12);
order = 'Reverse ASCII';
[chOut, ifail] = m01cc(ch, m1, l1, l2, order)
 

chOut = 

    'C05AZF  2181'
    'C05ADF  1351'
    'C02AEF   599'
    'A02ACF   531'
    'A02ABF   523'
    'A02AAF   289'
    'C05AGF   240'
    'C05AVF   211'
    'C05AXF   183'
    'C02ADF   169'
    'C05AJF   136'


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