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)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

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:     chm2 – cell array of strings
Elements m1 to m2 of ch must contain character data to be sorted.
Constraint: the length of each element of ch must not exceed 255.
2:     m1 int64int32nag_int scalar
The index of the first element of ch to be sorted.
Constraint: m1>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<l1l2LENch1.
5:     order – string (length ≥ 1)
If order='A', the values will be sorted into ASCII order.
If order='R', into reverse ASCII order.
Constraint: order='A' or '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: m2m1.

Output Parameters

1:     chm2 – cell array of strings
These values are rearranged into sorted order.
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,
orm1<1,
orm1>m2,
orl2<1,
orl1<1,
orl1>l2,
orl2>LENch1.
   ifail=2
On entry,order is not 'A' or 'R'.
   ifail=3
On entry,the length of each element of ch exceeds 255.
   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×logn, where n=m2-m1+1. The worst case time is proportional to n2, 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

This example reads a file of 12-character records, and sorts them into reverse ASCII order on characters 7 to 12.
function m01cc_example


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

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';
[ch, ifail] = m01cc(ch, m1, l1, l2, order);

fprintf('Records sorted on columns %2d to %2d:\n\n',l1,l2);
for j=1:numel(ch)
  fprintf('%s\n',char(ch{j}));
end


m01cc example results

Records sorted on columns  7 to 12:

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

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–2015