Prev: "Optional" Arguments in Fortran ??
Next: ifort warning in sign function
From: glen herrmannsfeldt on 23 Feb 2010 20:32
robin <robin_v(a)bigpond.com> wrote:
(snip, I wrote)

> | I wonder if it is possible to call qsort() from Fortran.

> Why bother?
> Quicksort is a relatively short procedure to code,
> and codes in Fortran are readily available.

Well, first I didn't say that there was a reason, but...

As far as I know Fortran still doesn't allow the pointer tricks
needed to implement something like C's qsort().

(Given a pointer to an array of an arbitrary type, generate
pointers to all the array elements without actually knowing
or needing to know in advance what that type is.)

Note that, despite the name and the fact that I noted it
in the previous post, there is no requirement that qsort()
implement the quicksort algorithm.

-- glen

From: Ron Shepard on 23 Feb 2010 21:27
In article <hm1vir$2vp$1(a)naig.caltech.edu>,
glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote:

> As far as I know Fortran still doesn't allow the pointer tricks
> needed to implement something like C's qsort().

You can write indexed sort routines (using any algorithm you want)
in which the sort routine never needs to look at the individual
array elements, it works only with the integer array indices. The
comparisons are a little more expensive this way (they need a
subroutine call each), but it results in a very flexible interface.

$.02 -Ron Shepard
From: glen herrmannsfeldt on 23 Feb 2010 21:57
Ron Shepard <ron-shepard(a)nospam.comcast.net> wrote:
> In article <hm1vir$2vp$1(a)naig.caltech.edu>,
> glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote:

>> As far as I know Fortran still doesn't allow the pointer tricks
>> needed to implement something like C's qsort().

> You can write indexed sort routines (using any algorithm you want)
> in which the sort routine never needs to look at the individual
> array elements, it works only with the integer array indices. The
> comparisons are a little more expensive this way (they need a
> subroutine call each), but it results in a very flexible interface.

qsort() does a call for each comparison, but it can do the swap itself.

I might see how to write one in Fortran that does a subroutine call
for comparison and one for each swap, if you can pass a pointer
to an arbitrary type (like C's void pointer).

One way to use qsort() is to pass an array of pointers to the
actual elements being sorted. It also works well with structures,
as long as the elements aren't too big. (Such that data movement
time dominates.)

Since Fortran now has C_FUNLOC(), though, it shouldn't be hard
to use qsort(). So far, I haven't managed to compile a
call with C_FUNLOC(), though.

-- glen

From: Ron Shepard on 23 Feb 2010 22:46
In article <hm24il$423$1(a)naig.caltech.edu>,
glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote:

> One way to use qsort() is to pass an array of pointers to the
> actual elements being sorted. It also works well with structures,
> as long as the elements aren't too big. (Such that data movement
> time dominates.)

This is what I meant by an indexed sort. You pass an integer array.
The actual data does not move, so data movement never dominates no
matter how large the elements are. It is only the integers that are
swapped, shifted, inserted, etc. This is all straightforward to do
in fortran, even f77, although f90 simplifies some of the details by
allowing user defined data types to be sorted and by keeping the
data type definitions localized in the same module as the comparison
routines.

$.02 -Ron Shepard
From: James Van Buskirk on 24 Feb 2010 00:04
"robin" <robin_v(a)bigpond.com> wrote in message
news:yaZgn.9422$pv.3490(a)news-server.bigpond.net.au...

> "glen herrmannsfeldt" <gah(a)ugcs.caltech.edu> wrote in message
> news:hlv6t2$7d7$3(a)naig.caltech.edu...

> | I wonder if it is possible to call qsort() from Fortran.

> Why bother?
> Quicksort is a relatively short procedure to code,
> and codes in Fortran are readily available.

For example,

C:\gfortran\clf\qsort>type qstest.f90
module ifaces
use ISO_C_BINDING
implicit none
interface
function getch() bind(C,name='getch')
use ISO_C_BINDING
implicit none
integer(C_INT) getch
end function getch
subroutine qsort(base, nmemb, size, compar) bind(C,name='qsort')
use ISO_C_BINDING
implicit none
type(C_PTR), value :: base
integer(C_SIZE_T), value :: nmemb
integer(C_SIZE_T), value :: size
type(C_FUNPTR), value :: compar
end subroutine qsort
end interface
end module ifaces

module funcs
use ISO_C_BINDING
implicit none
type, bind(C) :: mytype
integer(C_INT) key
real(C_FLOAT) data
end type mytype
interface operator(<=)
module procedure LessOrEqual
end interface operator(<=)
contains
function compar(v1, v2) bind(C)
integer(C_INT) compar
type(C_PTR), value :: v1, v2
type(mytype), pointer :: p1, p2

call C_F_POINTER(v1,p1)
call C_F_POINTER(v2,p2)
if(.NOT.(p1 <= p2)) then
compar = 1
else if(.NOT.(p2 <= p1)) then
compar = -1
else
compar = 0
end if
end function compar
function LessOrEqual(v1, v2)
logical LessOrEqual
type(mytype), intent(in) :: v1, v2

LessOrEqual = v1%key <= v2%key
end function LessOrEqual
end module funcs

program qstest
use ifaces
use funcs
use ISO_C_BINDING
implicit none
integer(C_SIZE_T) MAX
type(mytype), allocatable, target :: arr(:)
integer i
integer(C_INT) result
real harvest

MAX = 20
allocate(arr(MAX))
do i = 1, MAX
call random_number(harvest)
arr(i) = mytype(10*MAX*harvest, i)
end do
write(*,'(a)') 'Unsorted data:'
do i = 1, MAX
write(*,*) i,arr(i)
end do
write(*,'(a)',advance='no') 'Press any key to sort the values.'
result = getch()
call qsort(C_LOC(arr(1)), MAX, C_SIZEOF(arr(1)), C_FUNLOC(compar))
write(*,'()')
do i = 1, MAX
write(*,*) i,arr(i)
end do
end program qstest

C:\gfortran\clf\qsort>gfortran qstest.f90 -oqstest

C:\gfortran\clf\qsort>qstest
Unsorted data:
1 199 1.0000000
2 113 2.0000000
3 193 3.0000000
4 149 4.0000000
5 73 5.0000000
6 96 6.0000000
7 14 7.0000000
8 1 8.0000000
9 69 9.0000000
10 68 10.000000
11 43 11.000000
12 26 12.000000
13 180 13.000000
14 77 14.000000
15 89 15.000000
16 132 16.000000
17 3 17.000000
18 130 18.000000
19 129 19.000000
20 64 20.000000
Press any key to sort the values.
1 1 8.0000000
2 3 17.000000
3 14 7.0000000
4 26 12.000000
5 43 11.000000
6 64 20.000000
7 68 10.000000
8 69 9.0000000
9 73 5.0000000
10 77 14.000000
11 89 15.000000
12 96 6.0000000
13 113 2.0000000
14 129 19.000000
15 130 18.000000
16 132 16.000000
17 149 4.0000000
18 180 13.000000
19 193 3.0000000
20 199 1.0000000

Looking at the date of creation of the directory above, I probably
posted a generic qsort algorithm in Fortran on 04/24/2008.
Example adapted from
http://groups.engin.umd.umich.edu/CIS/course.des/cis400/c/sort.html

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end


First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: "Optional" Arguments in Fortran ??
Next: ifort warning in sign function