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: 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 < l1 \leq l2 \leq LEN (ch (1))$ .
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: $m2 \geq m1$ .

Output Parameters

1: $ch (m2)$ – 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$ ,
or	$m1 < 1$ ,
or	$m1 > m2$ ,
or	$l2 < 1$ ,
or	$l1 < 1$ ,
or	$l1 > l2$ ,
or	$l2 > LEN (ch (1))$ .

$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 \times \log (n)

, where

n = m2 - m1 + 1

. The worst case time is proportional to

n^{2}

, 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

12

Open in the MATLAB editor: m01cc_example

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