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_realvec_sort (m01ca)

Purpose

nag_sort_realvec_sort (m01ca) rearranges a vector of double numbers into ascending or descending order.

Syntax

[rv, ifail] = m01ca(rv, m1, order, 'm2', m2)
[rv, ifail] = nag_sort_realvec_sort(rv, m1, order, 'm2', m2)

Description

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

Optional Input Parameters

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

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     rv(m2) – double array
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.
  ifail = 2ifail=2
On entry,order is not 'A' or 'D'.

Accuracy

Not applicable.

Further Comments

The average time taken by nag_sort_realvec_sort (m01ca) 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.

Example

function nag_sort_realvec_sort_example
rv = [1.3;
     5.9;
     4.1;
     2.3;
     0.5;
     5.8;
     1.3;
     6.5;
     2.3;
     0.5;
     6.5;
     9.9;
     2.1;
     1.1;
     1.2;
     8.6];
m1 = int64(1);
order = 'Ascending';
[rvOut, ifail] = nag_sort_realvec_sort(rv, m1, order)
 

rvOut =

    0.5000
    0.5000
    1.1000
    1.2000
    1.3000
    1.3000
    2.1000
    2.3000
    2.3000
    4.1000
    5.8000
    5.9000
    6.5000
    6.5000
    8.6000
    9.9000


ifail =

                    0


function m01ca_example
rv = [1.3;
     5.9;
     4.1;
     2.3;
     0.5;
     5.8;
     1.3;
     6.5;
     2.3;
     0.5;
     6.5;
     9.9;
     2.1;
     1.1;
     1.2;
     8.6];
m1 = int64(1);
order = 'Ascending';
[rvOut, ifail] = m01ca(rv, m1, order)
 

rvOut =

    0.5000
    0.5000
    1.1000
    1.2000
    1.3000
    1.3000
    2.1000
    2.3000
    2.3000
    4.1000
    5.8000
    5.9000
    6.5000
    6.5000
    8.6000
    9.9000


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