suews_util_qsort.f95

Go to the documentation of this file.

! Recursive Fortran 95 quicksort routine
! sorts real numbers into ascending numerical order
! Author: Juli Rew, SCD Consulting (juliana@ucar.edu), 9/03
! Based on algorithm from Cormen et al., Introduction to Algorithms,
! 1997 printing
 
! Made F conformant by Walt Brainerd
 
MODULE qsort_c_module
 
   IMPLICIT NONE
   PUBLIC :: qsortc
   PRIVATE :: partition
 
CONTAINS
 
   RECURSIVE SUBROUTINE qsortc(A)
      REAL, INTENT(in out), DIMENSION(:) :: a
      INTEGER :: iq
 
      IF (SIZE(a) > 1) THEN
         CALL partition(a, iq)
         CALL qsortc(a(:iq - 1))
         CALL qsortc(a(iq:))
      END IF
   END SUBROUTINE qsortc
 
   SUBROUTINE partition(A, marker)
      REAL, INTENT(in out), DIMENSION(:) :: a
      INTEGER, INTENT(out) :: marker
      INTEGER :: i, j
      REAL :: temp
      REAL :: x ! pivot point
      x = a(1)
      i = 0
      j = SIZE(a) + 1
 
      DO
         j = j - 1
         DO
            IF (a(j) <= x) EXIT
            j = j - 1
         END DO
         i = i + 1
         DO
            IF (a(i) >= x) EXIT
            i = i + 1
         END DO
         IF (i < j) THEN
            ! exchange A(i) and A(j)
            temp = a(i)
            a(i) = a(j)
            a(j) = temp
         ELSEIF (i == j) THEN
            marker = i + 1
            RETURN
         ELSE
            marker = i
            RETURN
         END IF
      END DO
 
   END SUBROUTINE partition
 
END MODULE qsort_c_module