On Friday, March 9, 2018 at 10:24:51 AM UTC-5, Ev. Drikos wrote:
> ..
> Just for the record, in C++ that supports templates the implementation
> of the quicksort algorithm is indeed simpler, no code duplication:
> ..
Readers will note if brevity and no code duplication (or at least limited) is desired, perhaps with the notion it implies simplicity, the unlimited polymorphic facility in Fortran with CLASS(*) can be made use of, provided an implementation is put together for some generic operators <=, >=. etc. and toward a generic SWAP method. It is trivial effort, moreover it can one-time too.
module QsortC_m
! Based on
http://www.fortran.com/qsort_c.f95
! that makes use of Cormen et al., Introduction to Algorithms
implicit none
private
public :: QsortC
contains
recursive subroutine QsortC( A )
! argument list
class(*), intent(inout) :: A(:)
! local variables
integer :: iq
iq = 0
if ( size(A) > 1 ) then
call Partition(A, iq)
call QsortC( A(:iq-1) )
call QsortC( A(iq:) )
end if
return
end subroutine QsortC
subroutine Partition(A, marker)
! Elided is the availability of generic operators and swap
! that takes dummy unlimited polymorphic arguments, say as in
! use xx, only : operator (>=), operator (<=), swap
! argument list
class(*), intent(inout) :: A(:)
integer, intent(out) :: marker
! local variables
integer :: i
integer :: j
i = 0
j = size(A) + 1
do
j = j-1
do
if (A(j) <= A(1)) exit !<-- make use of generic comparison
j = j-1
end do
i = i+1
do
if (A(i) >= A(1)) exit !<-- make use of generic comparison
i = i+1
end do
if (i < j) then
! exchange A(i) and A(j)
call swap( A(i), A(j) ) !<-- make use of generic swap
else if (i == j) then
marker = i+1
return
else
marker = i
return
end if
end do
return
end subroutine Partition
end module QsortC_m
Not saying the above is optimal or efficient, just that it's another option. What's really needed is for Fortran 202X to provide a robust solution for generics that works with data types efficiently.
Anyways with the above, I can write a unit test such as
program p
use QsortC_m, only : QsortC
implicit none
! local variables
character(len=*), parameter :: fmtg="(*(g0.3,1x))"
integer, parameter :: r = 6
blk_1: block
integer :: x(r)
print fmtg, "Block 1"
x = [ 42, 999, -1, 0, 50, 12 ]
print fmtg, "initial array is ", x
call QsortC(x)
print fmtg, "sorted array is ", x
end block blk_1
print *
blk_2: block
double precision :: x(r)
print fmtg, "Block 2"
call random_number( x )
x = real( int(x*100.0D0), kind=kind(x) )
print fmtg, "initial array is ", x
call QsortC(x)
print fmtg, "sorted array is ", x
end block blk_2
print *
blk_3: block
character(len=1) :: x(r)
print fmtg, "Block 3"
x = [ character(len=1) :: "q", "w", "e", "r", "t", "y" ]
print fmtg, "Initial array is ", x
call QsortC(x)
print fmtg, "sorted array is ", x
end block blk_3
stop
end program p
and upon execution with either Intel Fortran or gfortran, get output such as:
Block 1
initial array is 42 999 -1 0 50 12
sorted array is -1 0 12 42 50 999
Block 2
initial array is 88.0 68.0 96.0 91.0 37.0 39.0
sorted array is 37.0 39.0 68.0 88.0 91.0 96.0
Block 3
Initial array is q w e r t y
sorted array is e q r t w y