Numerical Computing with Modern FortranRichard J. Hanson and Tim Hopkins |
Chapter 6: Recursion in Fortran
Source Code:
These executables illustrate a number of ways of implementing the quicksort algorithm using a number of the new facilities available from modern versions of Fortran. The impact of using recursion and function in-lining are considered along with mechanisms for making the sort procedure more flexible for the user. This includes the use of user-defined types and abstract data types.
Six executables may be generated using the makefile provided- QuickMain: uses quicksort.f90, QuickMain.f90.
This program times the use of the quicksort algorithm using function calls on arrays of random and already sorted data. The timing of already sorted data may be turned off.
- QuickMainIn: uses quicInline.f90, QuickMainIn.f90.
This program times the use of the quicksort algorithm with explicit in-line code on arrays of random and already sorted data. The timing of already sorted data may be turned off.
- qstypeSepMain: uses sortdef.f90, qstypeSep.f90, qstypeSepMain.f90.
This executable uses type bound procedures to define the functions used in the quicksort.
- qstypeExtMain: uses usersort.f90, sortdef.f90, qstypeExtMain.f90,
set_precision.f90.
This program extends the type sortdata used in test qstypeSep via a user supplied module usersort.
- concreteMain: uses sortElements.f90, concrete.f90, concreteMain.f90,
set_precision.f90.
This executable uses abstract data types to allow maximum flexibility for the user to define sorting on any sort of data and any type of sorting.
- concreteDriver: uses sortElements.f90, concrete.f90, concreteDriver.f90, set_precision.f90. This implementation uses abstract data types to allow maximum flexibility for the user to define sorting on any sort of data and any type of sorting.
Sample output from QuickMain
Sorts array of double precision reals into ascending order using explicit double precision arrays. Basic sorting operations implemented by function calls. Size Random Ratio Expected Sorted Ratio Expected 500 0.00 0.00 2500 0.00 0.00 6.29 0.00 0.00 25.00 12500 0.02 0.00 6.03 0.03 0.00 25.00 62500 0.06 4.00 5.85 0.34 11.00 25.00 312500 0.27 4.25 5.73 2.95 8.59 25.00
Sample output from QuickMainIn
Sorts array of double precision reals into ascending order using explicit double precision arrays. Basic sorting operations implemented as inline code. Size Random Ratio Expected Sorted Ratio Expected 500 0.00 0.00 2500 0.00 0.00 6.29 0.00 0.00 25.00 12500 0.00 0.00 6.03 0.00 0.00 25.00 62500 0.02 0.00 5.85 0.05 0.00 25.00 312500 0.06 4.00 5.73 0.45 9.67 25.00
Sample output from qstypeSepMain
Sorts array of double precision reals into ascending order using a basic type. Basic sorting operations implemented by function calls to type bound procedures. Size Random Ratio Expected Sorted Ratio Expected 500 0.00 0.00 2500 0.00 0.00 6.29 0.02 0.00 25.00 12500 0.02 0.00 6.03 0.03 2.00 25.00 62500 0.06 4.00 5.85 0.37 12.00 25.00 312500 0.33 5.25 5.73 2.56 6.83 25.00 1562500 1.09 3.33 5.64 24.77 9.68 25.00 7812500 6.19 5.67 5.56 278.85 11.26 25.00
Sample output from qstypeExtMain
Sorts array of double precision reals into ascending order using an extended type. Basic sorting operations implemented by function calls to type bound procedures. This run is NOT sorting already sorted data Switch on by setting the variable dosorted to TRUE Beware: this can cause long execution times Ignore last three columns of the output table Size Random Ratio Expected Sorted Ratio Expected 500 0.00 0.00 2500 0.00 0.00 6.29 0.00 0.00 25.00 12500 0.02 0.00 6.03 0.00 0.00 25.00 62500 0.06 4.00 5.85 0.00 0.00 25.00 312500 0.34 5.50 5.73 0.00 0.00 25.00 1562500 1.47 4.27 5.64 0.00 0.00 25.00 7812500 5.68 3.87 5.56 0.00 0.00 25.00
Sample output from concreteMain
Sorts array of double precision reals into ascending order using an abstract data type and interfaces. Basic sorting operations implemented by function calls to type bound procedures. This run is NOT sorting already sorted data Switch on by setting the variable dosorted to TRUE Beware: this can cause long execution times Ignore last three columns of the output table Size Random Ratio Expected Sorted Ratio Expected 500 0.00 0.00 2500 0.00 0.00 6.29 0.00 0.00 25.00 12500 0.00 0.00 6.03 0.00 0.00 25.00 62500 0.06 0.00 5.85 0.00 0.00 25.00 312500 0.34 5.50 5.73 0.00 0.00 25.00 1562500 1.45 4.23 5.64 0.00 0.00 25.00 7812500 5.60 3.86 5.56 0.00 0.00 25.00
Sample output from concreteDriver
Before sorting: 0.50000000E+01 0.40000000E+01 0.30000000E+01 0.20000000E+01 0.10000000E+01 0.10000000E+02 0.90000000E+01 0.80000000E+01 0.70000000E+01 0.60000000E+01 ----------------------------------- After sorting: 0.10000000E+01 0.20000000E+01 0.30000000E+01 0.40000000E+01 0.50000000E+01 0.60000000E+01 0.70000000E+01 0.80000000E+01 0.90000000E+01 0.10000000E+02 -----------------------------------------------------------------------