Manual Reference Pages - sort_quick_rx (3)
NAME
sort_quick_rx(3f) - [M_sort] indexed hybrid quicksort of an array (LICENSE:PD)
CONTENTS
Synopsis
Description
Background
Example
SYNOPSIS
subroutine sort_quick_rx(data,index)
! one of real,intent(in) :: data(:) doubleprecision,intent(in) :: data(:) integer,intent(in) :: data(:) character,intent(in) :: data(:) complex,intent(in) :: data(:)integer,intent(out) :: indx(size(data))
DESCRIPTION
A rank hybrid quicksort. The data is not moved. An integer array is generated instead with values that are indices to the sorted order of the data. This requires a second array the size of the input array, which for large arrays could require a significant amount of order. One major advantage of this method is that any element of a user-defined that is a scalar intrinsic can be used to provide the sort data and subsequently the indices can be used to access the entire user-defined type in sorted order. This makes this seemingly simple sort procedure usuable with the vast majority of user-defined types.
BACKGROUND
From Leonard J. Moss of SLAC:Here’s a hybrid QuickSort I wrote a number of years ago. It’s based on suggestions in Knuth, Volume 3, and performs much better than a pure QuickSort on short or partially ordered input arrays.
This routine performs an in-memory sort of the first N elements of array DATA, returning into array INDEX the indices of elements of DATA arranged in ascending order. Thus,
DATA(INDX(1)) will be the smallest number in array DATA; DATA(INDX(N)) will be the largest number in DATA.The original data is not physically rearranged. The original order of equal input values is not necessarily preserved.
sort_quick_rx(3f) uses a hybrid QuickSort algorithm, based on several suggestions in Knuth, Volume 3, Section 5.2.2. In particular, the "pivot key" [my term] for dividing each subsequence is chosen to be the median of the first, last, and middle values of the subsequence; and the QuickSort is cut off when a subsequence has 9 or fewer elements, and a straight insertion sort of the entire array is done at the end. The result is comparable to a pure insertion sort for very short arrays, and very fast for very large arrays (of order 12 micro-sec/element on the 3081K for arrays of 10K elements). It is also not subject to the poor performance of the pure QuickSort on partially ordered data.
Complex values are sorted by the magnitude of sqrt(r**2+i**2).
o Created: sortrx(3f): 15 Jul 1986, Len Moss o saved from url=(0044)http://www.fortran.com/fortran/quick_sort2.f o changed to update syntax from F77 style; John S. Urban 20161021 o generalized from only real values to include other intrinsic types; John S. Urban 20210110
EXAMPLE
Sample usage:
program demo_sort_quick_rx use M_sort, only : sort_quick_rx implicit none integer,parameter :: isz=10000 real :: rr(isz) integer :: ii(isz) integer :: i write(*,*)’initializing array with ’,isz,’ random numbers’ CALL RANDOM_NUMBER(RR) rr=rr*450000.0 write(*,*)’sort real array with sort_quick_rx(3f)’ call sort_quick_rx(rr,ii) write(*,*)’checking index of sort_quick_rx(3f)’ do i=1,isz-1 if(rr(ii(i)).gt.rr(ii(i+1)))then write(*,*)’Error in sorting reals small to large ’,i,rr(ii(i)),rr(ii(i+1)) endif enddo write(*,*)’test of sort_quick_rx(3f) complete’ ! use the index array to actually move the input array into a sorted order rr=rr(ii) do i=1,isz-1 if(rr(i).gt.rr(i+1))then write(*,*)’Error in sorting reals small to large ’,i,rr(i),rr(i+1) endif enddo write(*,*)’test of sort_quick_rx(3f) complete’ end program demo_sort_quick_rx
Results:
initializing array with 10000 random numbers sort real array with sort_quick_rx(3f) checking index of sort_quick_rx(3f) test of sort_quick_rx(3f) complete test of sort_quick_rx(3f) complete
| sort_quick_rx (3) | March 11, 2021 |
