Module name: sort_mod
Author: Clive Page (University of Leicester, cgp@star.le.ac.uk)
This module contains subroutines to sort a data array into ascending order using Hoare's quick-sort algorithm. There is a generic interface which supports data types INTEGER, REAL, DOUBLE PRECISION, and CHARACTER (any length).
The simplest call is:
CALL quick_sort(array)
The array argument has INTENT(INOUT) and returns the data sorted into ascending order.
In some cases it is desirable to know the original order of the data points, for example to sort another array in the same way. In this case an optional second argument may be given; it returns an integer array of the same size containing numbers in the range 1 to size(array) which tell you the original position of each element returned sorted. For example if you do:
unsorted_array = array call quick_sort(array, index)
then unsorted_array(index(i)) = array(i) for all i in [lbound(array), ubound(array)]. Note that array is always returned sorted, whether index is supplied or not. This can be something to be careful of. Suppose you have a data structure array which you want to sort in order of one of its constituents, for example a structure that stores gtis:
type :: gtiType
real(kind(0d0)) :: time
logical :: isStart
end type gtiType
type(gtiType) :: gtiArray(100)
! Fill gtiArray
In this case to sort the logicals as well you will need to do something like the following:
type(gtiType) :: temp_gtiArray(size(gtiArray))
temp_gtiArray%time = gtiArray%time
call quick_sort(temp_gtiArray%time, index)
do i = 1, size(gtiArray)
temp_gtiArray(i)%isStart = gtiArray(index(i))%isStart
! NOT temp_gtiArray(i) = gtiArray(index(i))!! The times are already sorted.
end do
gtiArray = temp_gtiArray
Note that the quick-sort algorithm is on average about twice as fast as heap-sort but becomes much slower for special cases. This quick-sort algorithm was designed to cope with nearly-sorted data as well as random data without any significant degradation in speed. Note that it is not a stable sort, i.e. equal values will not necessarily remain in the same relative order.
