warning 676 in recursive routines

Hi , i have a recursive routine (quicksort) that works correctly but give argument type warnings. Am i doing something wrong or is this a glitch in the compiler

thanks

steve

RECURSIVE SUBROUTINE QUICKSORTDP_index(RARRAY,index, LOW, IHIGH)

INTEGER LOW, IHIGH, IPIVOT DOUBLE PRECISION RARRAY( * ) integer index(*)

IF (LOW .LT. IHIGH) THEN CALL QSRT_PARTITIONDP_index(RARRAY,index, LOW, IHIGH, IPIVOT) CALL QUICKSORTDP_index(RARRAY,index, LOW, IPIVOT - 1) CALL QUICKSORTDP_index(RARRAY,index, IPIVOT + 1, IHIGH) ENDIF

end

D:\apps_cpi\sprint\sprint.FOR(1592) : warning 676 - In a call to QUICKSORTDP_INDEX from another procedure, the first argument was of type REAL(KIND=2), it is now REAL(KIND=2) D:\apps_cpi\sprint\sprint.FOR(1592) : warning 676 - In a call to QUICKSORTDP_INDEX from another procedure, the second argument was of type INTEGER(KIND=3), it is now INTEGER(KIND=3) D:\apps_cpi\sprint\sprint.FOR(1592) : warning 676 - In a call to QUICKSORTDP_INDEX from another procedure, the third argument was of type INTEGER(KIND=3), it is now INTEGER(KIND=3) D:\apps_cpi\sprint\sprint.FOR(1592) : warning 676 - In a call to QUICKSORTDP_INDEX from another procedure, the fourth argument was of type INTEGER(KIND=3), it is now INTEGER(KIND=3)

Steve,

I am guessing here, but if QUICKSORTDP_index and QSRT_PARTITIONDP_index are not contained within a module, since you have assumed size arrays (*), then the recursive QUICKSORTDP_index requires an interface block for QSRT_PARTITIONDP_index.

Ken

Steve

Please provide a short main program that illustrates the issue.

Hi Paul

thanks for the response. here is a working example

regards

steve

	program test
    	implicit none			
		integer iarray(7)			
		integer n_item,ij
		
         n_item = 7
    iarray(1) = 7
    iarray(2) = 3
    iarray(3) =  2
    iarray(4) = 1
    iarray(5) =4
    iarray(6) =  9
    iarray(7) = 6
		call   QUICKSORTI(IARRAY, 1, n_item)		
		do 10 ij = 1, n_item
		write(*,*) ij , ' ' ,iarray(ij)

10 continue end

  RECURSIVE SUBROUTINE QUICKSORTI(IARRAY, LOW, IHIGH)

! ===================== IMPLICIT NONE INTEGER IARRAY( * ), LOW, IHIGH, IPIVOT IF (LOW .LT. IHIGH) THEN CALL QSRT_PARTITIONI(IARRAY, LOW, IHIGH, IPIVOT) CALL QUICKSORTI(IARRAY, LOW, IPIVOT - 1) CALL QUICKSORTI(IARRAY, IPIVOT + 1, IHIGH) ENDIF END

  SUBROUTINE QSRT_PARTITIONI(IARRAY, LOW, IHIGH, IPIVOT)

! ========================== IMPLICIT NONE INTEGER IARRAY( * ), LOW, IHIGH, IPIVOT, PIVOT_VALUE, I, J,temp PIVOT_VALUE = IARRAY(IHIGH) ! Use the last element as pivot I = LOW - 1 DO 10 J = LOW, IHIGH - 1 IF (IARRAY(J) .LE. PIVOT_VALUE) THEN I = I + 1 TEMP = iarray(I) iarray(I) = iarray(J) iarray(J) = TEMP
ENDIF 10 CONTINUE TEMP = iarray(I + 1) iarray(I + 1) = iarray(iHIGH) iarray(iHIGH) = TEMP IPIVOT = I + 1 END

This is a false warning that has been removed for the next release of FTN95.

Hi Paul

thanks for the quick response.

regards

steve

So my guess, was way out - again.

Adding (kind=3) to all integer declarations removes the warning.

program test
implicit none
integer(kind=3) iarray(7)
integer(kind=3) n_item,ij

n_item = 7
iarray(1) = 7
iarray(2) = 3
iarray(3) = 2
iarray(4) = 1
iarray(5) =4
iarray(6) = 9
iarray(7) = 6
call QUICKSORTI(IARRAY, 1, n_item)
do 10 ij = 1, n_item
write(*,*) ij , ' ' ,iarray(ij)
10 continue
end



RECURSIVE SUBROUTINE QUICKSORTI(IARRAY, LOW, IHIGH)
! =====================
IMPLICIT NONE
INTEGER(kind=3) IARRAY( * ), LOW, IHIGH, IPIVOT
IF (LOW .LT. IHIGH) THEN
CALL QSRT_PARTITIONI(IARRAY, LOW, IHIGH, IPIVOT)
CALL QUICKSORTI(IARRAY, LOW, IPIVOT - 1)
CALL QUICKSORTI(IARRAY, IPIVOT + 1, IHIGH)
ENDIF
END

SUBROUTINE QSRT_PARTITIONI(IARRAY, LOW, IHIGH, IPIVOT)
! ==========================
IMPLICIT NONE
INTEGER(kind=3) IARRAY( * ), LOW, IHIGH, IPIVOT, PIVOT_VALUE, I, J,temp
PIVOT_VALUE = IARRAY(IHIGH) ! Use the last element as pivot
I = LOW - 1
DO 10 J = LOW, IHIGH - 1
IF (IARRAY(J) .LE. PIVOT_VALUE) THEN
I = I + 1
TEMP = iarray(I)
iarray(I) = iarray(J)
iarray(J) = TEMP
ENDIF
10 CONTINUE
TEMP = iarray(I + 1)
iarray(I + 1) = iarray(iHIGH)
iarray(iHIGH) = TEMP
IPIVOT = I + 1
END

H i ken

thanks for the feedback

I still depend on some ancient fortran 77 code analysers (aka Luddite or too mean to invest in the latest products...) so i void using F95 syntax. If i need anything elaborate i tend to use C++

It is also easier for the junior engineers i work with to understand what is going on as their coding skills have drastically declined over the 40 old years I've been trying to get computers to do what is required

regards

steve

Hi Steve, ken,

The revised code runs as expected. I do think that keeping the f95 syntax clear and with plenty of comment lines makes for easier code for learners to follow.

My update to the code would have the terminations in place, e.g. end program test, end subroutine A etc. Also do loops are much cleaner in Fortran 95 now, where we can do the following:

do ij = 1, n_item write(,) ij , ' ' ,iarray(ij) end do

Good to highlight the recursive functionality.

Code tested on ftn95 version 9.05.0.0

Lester

The high pivot selection fails badly if there is an ordered set of values. I have enhanced the code to demonstrate this with real*8 values

  program testd
    implicit none
    real*8, allocatable :: varray(:)
    integer :: n_item,ij, ne, np, no,k
    logical :: echo_partition = .false.

    n_item = 88888000  

    write (*,11) delta_sec()
    Write (*, 10) 'Sort test for size = ',n_item
    allocate ( varray(n_item) )

   Write (*, 10, advance='NO') 'Initialising'
    n_item = size (varray)
    call random_number (varray )
    write (*,11) delta_sec()

  do k = 1,2    ! k=2 tests ordered set

   Write (*, 10, advance='NO') 'Sorting'
    np = 0
    no = 0

    call QUICKSORTD (vARRAY, 1, n_item)
    write (*,11) delta_sec()

    write (*,*) n_item,' items sorted'
    write (*,*) np,' partitions'
    write (*,*) no,' all shift'

   Write (*, 10, advance='NO') 'Checking'
    ne = 0
    do ij = 1, n_item-1
      if ( varray(ij) <= varray(ij+1) ) cycle
      write (*,*) ij , ' ' ,varray(ij),varray(ij+1)
      ne = ne+1
    end do
    write (*,11) delta_sec()
    write (*,*) ne,' order errors'

  end do
     
 10 format (/a,i0)
 11 format (2x,f0.4)

  contains
  
    RECURSIVE SUBROUTINE QUICKSORTD (DARRAY, LOW, IHIGH)
      IMPLICIT NONE
      real*8 :: DARRAY(*)
      INTEGER LOW, IHIGH, IPIVOT

      IF (LOW < IHIGH) THEN
        CALL QSRT_PARTITIOND (DARRAY, LOW, IHIGH, IPIVOT)
        CALL QUICKSORTD      (DARRAY, LOW,        IPIVOT - 1)
        CALL QUICKSORTD      (DARRAY, IPIVOT + 1, IHIGH)
      END IF

    END SUBROUTINE QUICKSORTD

    SUBROUTINE QSRT_PARTITIOND (DARRAY, LOW, HIGH, IPIVOT)
      IMPLICIT NONE
      real*8 :: DARRAY(*),  PIVOT_VALUE, dtemp
      INTEGER LOW, HIGH, IPIVOT, I, J, ns, nk
      logical :: use_mid_value = .true.

  !  mid value is much better for sorting an ordered set
      if ( use_mid_value ) then
        if ( high - low  > 1 ) then
          ipivot = (low+high) / 2
          dtemp  = darray(IPIVOT)
          darray(IPIVOT) = darray(HIGH)
          darray(HIGH)   = dtemp
        end if
      end if

      PIVOT_VALUE = DARRAY(HIGH) ! Use the last element as pivot

      I = LOW - 1
      ns = 0
      nk = 0
      DO J = LOW, HIGH - 1
        IF (DARRAY(J) > PIVOT_VALUE) CYCLE
        I = I + 1
        if ( i /= j ) then
          dtemp = darray(J)
          darray(J) = darray(I)
          darray(I) = dtemp
          ns = ns+1
        else
          nk = nk+1
        end if
      END DO

      IPIVOT = I + 1
      if ( IPIVOT /= HIGH ) then
        dtemp = darray(IPIVOT)
        darray(IPIVOT) = darray(HIGH)
        darray(HIGH)   = dtemp
        if ( echo_partition ) write (*,*) 'partition', LOW, HIGH, ns, nk
        np = np+1
      else
        if ( echo_partition ) write (*,*) 'no pivot switch', nk, high-low
        no = no+1
      end if

    END SUBROUTINE QSRT_PARTITIOND

    real function delta_sec ()
      integer*8 :: tick, rate, last_tick = 0
      real      :: sec
      call system_clock ( tick, rate )
      sec = real ( tick-last_tick ) / real ( rate )
      last_tick = tick
      delta_sec = sec
    end function delta_sec

  end program testd

see 'use_mid_value = .true.' but reduce n_item !

Thanks for sharing the revised code John.

Lester

The quicksort theory states the worst case is for an ordered set

ref: https://www.geeksforgeeks.org/quick-sort-algorithm/

Time Complexity:

Best Case: (Ω(n log n)), Occurs when the pivot element divides the array into two equal halves. Average Case (θ(n log n)), On average, the pivot divides the array into two parts, but not necessarily equal. Worst Case: (O(n²)), Occurs when the smallest or largest element is always chosen as the pivot (e.g., sorted arrays).

i'll look at updating my code to use the mid value as the pivot

thanks

steve

Quoted from steveDoyle The quicksort theory states the worst case is for an ordered set

I am not sure of the source of that claim, however you can easily show the difference between 'high' pivot and 'mid_point' pivot with the program I provided.

'high' pivot fails badly for an ordered set of values, while 'mid_point' pivot removes the worst case is for an ordered set problem.

So to demonstrate this, choose a smaller value for n_items, say 100000 (you will see why) set use_mid_value = .false. run with these options then set use_mid_value = .true.

The statistics are interesting, which may take some time to understand.

The other main changes that can be done to the quick_sort are :

1. Include a bubble sort for when high-low < say 6. This can sometimes improve, but now only slightly with the latest FTN95 /64 compiler
2. convert to an indexed sort, so that the original 'DARRAY'data is not altered. There was a time when swapping the index values was faster than swapping the darray values, but that has also gone away.
3. replace recursion with a partition list in a DO loop.

The sort I use has replaced recursion with a list of partition pairs, which replaced the recursive stack with a list of low/high.

The remaining problem with quick sort is how to split the list darray(low:high) into darray(low:pivot-1), darray(pivot) and darray(pivot+1:high) efficiently, while not loosing the previous order of values. I have seen some use of the intrinsic PACK, which is neat, but not the most efficient for data movement, as it requires a double scan or temporary arrays to be merged.

I posted the program, as I thought the statistics it recovers are interesting, (and could be improved for the ordered case)

I have created a variant of the indexed quick sort, which may be of interest.

This is: An indexed sort that does not change the original data order. This is still a recursive sort. In the partitioning, I have experimented with the high-low lists where I overwrite the index(low:) with the values < pivot_value, but have a temporary array to store the high value pointers. I have 2 versions of the partitioning; a temporary stack array for the array < 800 kBytes and an alternative heap array for larger tests. (Gfortran has a smaller stack problem, but FTN95 does not) I have included a bubble sort for small partitions ( entries < 5 ), although it does not have as great affect that it did. (run times can vary a bit, independent of bubble size?) I have allowed for different pivot selection. I have included statistics to give some indication of the relative scan approaches and include identifying when a partition does not change the order of entries. I have not paid attention to repeated values, which can be further sorted by their order in the list.

It may provide a platform to test some other alternatives or further investigate pivot selections.

I have always found quick_sort to be very robust, especially when choosing a central pivot value.

https://www.dropbox.com/scl/fi/eb0gvx4w0t2773ujwci74/steve_sort_id.f90?rlkey=uyutn439deehcvgee2iloqme4&st=s4d2gd6u&dl=0

Let me know if you find any improvements in this code.

John

John,

You might want to look at this implementation, which is the fastest I have seen for large data sets. It sorts the input array and also returns index values.

https://github.com/gher-uliege/OAK/blob/master/quicksort.f90

Hi Ken & Steve,

I have looked at both quicksort codes you posted and also my non-recursive quick sort which uses a DO loop.

They differ in a number of areas, being 1: Selection of pivot for spliting 2: Order of performing sub-sorts to minimise stack 3: Use of bubble or insertion sort for small sort lists 4: Use of indexing to not modify ARRAY 5: Handling of repeated values

1: Selection of pivot for splitting Ken's sort uses a median value of 3 options (low:mid:high) Steve's sort selects the high value, which is a very bad option, especially for an ordered data set. (will produce a stack overflow for large sorted data sets) My sort selects the mid value, while I have experimented with median of 3 or median of 5 on a set of random values. Effectively this is a median of 1, 3 or 5 possibilities. Unfortunately, no median pivot selection strategy appears to be significantly better for the data sets I have tested, so I am tempted to change to median of 5 as it may suit some skewed data sets I have not tested(?)

2: Order of sub-sorts to minimise stack Once the data set has been partitioned into 2 subsets, each subset is in turn quick-sorted. However to minimise the stack growth, the smaller subset should be sorted first. This minimises the stack growth and can be significant for skewed data sets.

3: Use of bubble or insertion sort for small sort lists. This is a good option to revert to a simpler and quicker sort for small lists. It can be very effective for quick sorts of small sub-sets ( say less than 5 ) but in the past has provided marginal improvement when sub-sets > 10. Ken's example of using an insertion sort of up to 45 is new to me, although may relate to the indexing attribute or recent changes in machine instructions. The optimum number can range between 10 and 45, depending on processor or data characteristics. I have found little difference between a bubble or insertion sort.

4: Use of indexing to not modify ARRAY I have always preferred an indexed sort, as it does not modify the data ARRAY. Indexing does come with a performance penalty, which can be about 50% extra time. However indexed sorts that don't change the original data provide more information that suits my applications.

5: Handling of repeated values To order repeated values, I sort both the value and it's position (index), which is unique for each value. Again this comes with a performance penalty, but can be important for strategies that relate to order of values.

Quicksort is claimed to be bad for ordered data sets (which the high pivot choice demonstrates) although both Ken's example amd my approach eliminate this problem.

I have been using the quicksort strategies I have identified for over 30 years, although mainly in finite element equation ordering. Unfortunalely the testing I have done is with a set of random generated values, which does not identify some corner or unusual data cases. There will probably be other data cases that are less suitable for my strategies, so it is good to know what can be changed.

John,

Thanks for sharing this summary of your observations on this which are very useful.

This is clearly a thought provoking thread.

I have been experimenting with a random pivot. I don't see any performance gain although AI suggests I should.

Quoted from Kenneth_Smith although AI suggests I should.

I wonder what AI would suggest about Quicksort and pre-ordered sets ? The classic response would probably be it fails, but I have found attention to pivot selection and sorting the smallest sub-set first eliminates this issue.

It can also be difficult when testing to generate corner cases. So perhaps others may help here.

Long ago I tested sorts on arrays of thousands, but now hundreds of millions. The next problem may occur shortly when calculating median = (low+high)/2 produces integer overflow !

This thread reminded me of an impressive paper by Bentley and McIlroy, https://www.cs.dartmouth.edu/~doug/mdmspe.pdf in which they show how to design a killer adversary for quicksort if the input list is allowed to be composed on the fly. The message was that if one does not specify the rules tightly, any otherwise excellent algorithm can fail on some input data that the creators of the algorithm did not plan for!

John,

The problem with using AI is you have to learn to ask the correct questions!

Here's my final attempt at this problem (for now anyway!)

https://www.dropbox.com/scl/fi/0aywa3cwvjjk2onx4hkke/Qsort.f95?rlkey=f9phwyvb2gn7zcqyaftwg6ysn&st=bzea9n6s&dl=0

! QSR8 (ARR) Returns sorted array ! ! QSR8WITHP (ARR, P) Returns sorted array and pointers to original unsorted array. Size(ARR) must equal Size(P) ! ! QSR8ONLYP (ARR, P) Does not modify the array but returns pointers. Size(ARR) must equal Size(P)

These subroutines are faster than using QSORTD from the NSWL which I have used for many years.

How the Sorting Process Works

Recursive Sorting of the Smaller Partition:

The recursive subroutine always recurses into the smaller partition to reduce the recursion depth. This is done for efficiency, as it minimizes the maximum depth of the call stack (which is proportional to log(n) in the best case for a balanced quicksort). After the recursive call completes, the smaller partition is fully sorted.

Iterative Sorting of the Larger Partition:

Instead of immediately recursing into the larger partition, the code updates the bounds (l or r) to point to the larger partition and continues the loop (do while (l < r)). This means the larger partition is handled iteratively in the subsequent iterations of the do while loop. By avoiding recursion here, the algorithm effectively processes the larger partition without adding to the call stack.

Progressive Reduction of the Problem Space:

After sorting the smaller partition via recursion and adjusting l or r to handle the larger partition, the algorithm reduces the size of the problem in each iteration. Eventually, all partitions are processed (either recursively or iteratively). The loop ensures that every subpartition is handled, either by recursion or by the iterative logic within the do while loop.

Why This Works

Tail Call Optimization:

After the smaller partition is sorted recursively, the subroutine does not return immediately. Instead, it continues to handle the larger partition iteratively by adjusting the bounds (l or r). Tail call optimization prevents the need for additional recursive calls, ensuring that the larger partition gets processed within the same subroutine invocation.

Loop Completeness:

The do while (l < r) loop guarantees that every part of the array will be processed until the entire range [left, right] is sorted. Even though the smaller partition is handled recursively, the larger partition is sorted through subsequent iterations of the loop.

In this case AI was very helpful! Although it's answer (above) to my question 'How does the Sorting Process Work' is perhaps a little verbose.