PDA_QSIDx - Sort an array of pointers to access an array in descending order

Description:

The routine uses the QUICKSORT algorithm to permute an array of pointers so that they access an associated array of values in descending order. The ``median of three'' modification is included to reduce the likelihood of encountering the worst-case behaviour of QUICKSORT.

The routine exists for types REAL (x=R), DOUBLE PRECISION (x=D), and INTEGER (x=I).

Invocation:

CALL PDA_QSIDx( EL, X, IP )

Arguments:

EL = INTEGER (Given)

The number of pointers to be permuted.

X( EL ) = TYPE (Given)

The array to be sorted.

IP( EL ) = INTEGER (Given and Returned)

The indices of the elements of X in sorted order (i.e. IP( 1 ) gives the index into X of the highest value).

References

Sedgwick, R., 1988, Algorithms (Addison-Wesley).

Timing

If N elements are to be sorted, the average time goes as N*ln(N). The worst-case time goes as N**2.

Copyright

Copyright (C) 1992 Science & Engineering Research Council