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_intvec_sort (m01cb)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

nag_sort_intvec_sort (m01cb) rearranges a vector of integer numbers into ascending or descending order.

Syntax

[iv, ifail] = m01cb(iv, m1, order, 'm2', m2)
[iv, ifail] = nag_sort_intvec_sort(iv, m1, order, 'm2', m2)

Description

nag_sort_intvec_sort (m01cb) 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.

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:     ivm2 int64int32nag_int array
Elements m1 to m2 of iv must contain integer values to be sorted.
2:     m1 int64int32nag_int scalar
The index of the first element of iv to be sorted.
Constraint: m1>0.
3:     order – string (length ≥ 1)
If order='A', the values will be sorted into ascending (i.e., nondecreasing) order.
If order='D', into descending order.
Constraint: order='A' or 'D'.

Optional Input Parameters

1:     m2 int64int32nag_int scalar
Default: the dimension of the array iv.
The index of the last element of iv to be sorted.
Constraint: m2m1.

Output Parameters

1:     ivm2 int64int32nag_int array
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.
   ifail=2
On entry,order is not 'A' or 'D'.
   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.

Example

This example reads a list of integers and sorts them into descending order.
function m01cb_example


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

iv = [int64(23) 45 45 67 69 90 999 1 78 112 24 69 96 99 45 78];
m1 = int64(1);
order = 'Descending';

[iv, ifail] = m01cb(iv, m1, order);

fprintf('Sorted numbers:\n\n');
fprintf('%5d%5d%5d%5d%5d%5d%5d%5d\n',iv);


m01cb example results

Sorted numbers:

  999  112   99   96   90   78   78   69
   69   67   45   45   45   24   23    1

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