[UP]

Manual Reference Pages  - sort_quick_rx (3)

NAME
sort_quick_rx(3f) - [M_sort] indexed hybrid quicksort of a real array

CONTENTS

Synopsis
Description
Example

SYNOPSIS
subroutine sort_quick_rx(data,index) 

      real,intent(in)         :: data(:)
      integer,intent(out)     :: indx(size(data))

DESCRIPTION

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.
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

EXAMPLE
Sample usage: 

   program demo_sort_quick_rx
   use M_sort, only : sort_quick_rx
   implicit none
   integer,parameter            :: isz=10000000
   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’
   end program demo_sort_quick_rx

sort_quick_rx (3) October 17, 2020
Generated by manServer 1.08 from 9a7a3c23-00b5-4d7d-90e9-337ba82447a8 using man macros.