---

C Library Functions  - sort_quick_rx (3)

---

NAME

sort_quick_rx(3f) - [M_sort:sort:quicksort] indexed hybrid quicksort of an array (LICENSE:PD)

CONTENTS

Synopsis
Description
Background
Examples

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 memory. One major advantage of this method is that any element of a user-defined type 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

EXAMPLES

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

---

Nemo Release 3.1

sort_quick_rx (3)

February 23, 2025

Generated by manServer 1.08 from 6d93f58a-6aec-4423-b68a-9b3a5626bfa2 using man macros.