! Test5.f95

! Recursive Fortran 95 quicksort routine
! sorts integer 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

! QsortC uses quicksort to print array A in sorted order with the indicated 
! size. The array elements of the actual parameter are not physically
! rearranged.

RECURSIVE INTEGER FUNCTION QsortC (A, sizeA) RESULT (result)
  INTEGER A (100), sizeA
  INTEGER B (100)
  INTEGER iq, i, j, temp
  INTEGER x      ! pivot point
  INTEGER QsortCValue
  INTEGER return1, return2, return3 ! exit flags for loops

  IF (sizeA .GT. 1) THEN
    x = A (1)
    i = 0
    j = sizeA + 1
    return1 = 0
    DO WHILE (return1 .EQ. 0)
      
      j = j - 1
      return2 = 0
      DO WHILE (return2 .EQ. 0)
        IF (j .GT. 0) THEN
          IF (A (j) .GT. x) THEN
            j = j - 1
          ELSE
            return2 = 1
          END IF
        ELSE
          return2 = 1
        END IF
      END DO

      i = i + 1
      return3 = 0
      DO WHILE (return3 .EQ. 0)
        IF (i .LE. sizeA) THEN
          IF (A (i) .LT. x) THEN
            i = i + 1
          ELSE
            return3 = 1
          END IF
        ELSE
          return3 = 1
        END IF
      END DO

      IF (i .LT. j) THEN
        ! exchange A (i) and A (j)
        temp  = A (i)
        A (i) = A (j)
        A (j) = temp
      ELSE
        IF (i .EQ. j) THEN
          iq = i + 1
          return1 = 1
        ELSE
          iq = i
          return1 = 1
        END IF
      END IF
    END DO

    QsortCValue = QsortC (A, iq - 1)	! quick sort elements from 1 .. iq - 1
    i = iq
    j = 0
    DO WHILE (i .LE. sizeA)
      j = j + 1
      B (j) = A(i)
      i = i + 1
    END DO
    QsortCValue = QsortC (B, j)		! quick sort elements from iq .. sizeA
  ELSE
    PRINT *, A (sizeA)
  END IF
  result = 0 

  RETURN 
END

! Test5 is a driver program which builds a test array and passes it to the
! QsortC function.

PROGRAM Test5
  INTEGER i, r, QsortCValue
  INTEGER myarray (100)
  r = 10
  myarray ( 1) =  0
  myarray ( 2) = 50
  myarray ( 3) = 20
  myarray ( 4) = 25
  myarray ( 5) = 90
  myarray ( 6) = 10
  myarray ( 7) =  5
  myarray ( 8) =  1
  myarray ( 9) = 99
  myarray (10) = 75
  QsortCValue = QsortC (myarray, r)
  STOP
END