forums.silverfrost.com

[steveDoyle]

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)

[Kenneth_Smith]

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

[PaulLaidler]

Steve

Please provide a short main program that illustrates the issue.

[steveDoyle]

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

[PaulLaidler]

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

[steveDoyle]

Hi Paul

thanks for the quick response.

regards

steve

[Kenneth_Smith]

So my guess, was way out - again.

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

[steveDoyle]

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

[arctica]

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

[JohnCampbell]

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

[arctica]

Thanks for sharing the revised code John.

Lester

[steveDoyle]

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

[JohnCampbell]

[JohnCampbell]

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

[Kenneth_Smith]

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