Hi everyone, I am in need of some assisstance to modify the quicksort algorithm given in "chapter B8-Sorting". This is given by the subroutine Sort(arr).

There is an obsolete pdf version online, if it helps to refer to : http://www.nrbook.com/a/bookf90pdf/chap8f9.pdf, page 3.

I have 2 arrays both of the same dimension and rank, each element of the same order are interelated properties, e.g. in 1 array there are velocity magnitudes, in the other one I have probability densities. so 1 magnitude ties with 1 density, I need to sort the velocity array into ascending numerical order, and rearrange the probability array into the same exact order.

In other words,

If velocity i,j,k have probs a,b,c respctively, when I rearrange velocity array into k,i,j, I want the probability array to automatically arrange to c,a,b.

It's probably just adding more swap function calls but I'm not sure where to add them, and there are lots of swap functions I am not sure which ones to use!

Thank you for your help, anything is appreciated.

Yameng

...
I have 2 arrays both of the same dimension and rank, each element of the same order are interelated properties...
Ummm...

Isn't that exactly what sort2 is for?


!
! Demonstration of use of sort2
!
! davekw7x
!
PROGRAM xsort2

USE nrtype
USE nrutil
USE nr

IMPLICIT NONE
INTEGER(I4B), PARAMETER :: N=10
INTEGER(I4B) :: i

REAL(SP), DIMENSION(N) :: a,b

a = (/ 9.0, 7.0, 3.0, 4.0, 2.0, 6.0, 0.0, 5.0, 8.0, 1.0 /)
b = (/ 6.0, 0.0, 8.0, 9.0, 2.0, 7.0, 5.0, 1.0, 3.0, 4.0 /)

write(*, '("Initially:"/" A B")')
do i=1,N
write(*,'(1x,2f7.1)') a(i), b(i)
end do

call sort2(a,b)

write(*, '(/"After sorting on A:"/" A B")')
do i=1,N
write(*,'(1x,2f7.1)') a(i), b(i)
end do

call sort2(b,a)

write(*, '(/"After sorting on B:"/" A B")')
do i=1,N
write(*,'(1x,2f7.1)') a(i), b(i)
end do

END PROGRAM xsort2


Output (compiled with GNU gfortran):

Initially:
A B
9.0 6.0
7.0 0.0
3.0 8.0
4.0 9.0
2.0 2.0
6.0 7.0
0.0 5.0
5.0 1.0
8.0 3.0
1.0 4.0

After sorting on A:
A B
0.0 5.0
1.0 4.0
2.0 2.0
3.0 8.0
4.0 9.0
5.0 1.0
6.0 7.0
7.0 0.0
8.0 3.0
9.0 6.0

After sorting on B:
A B
7.0 0.0
5.0 1.0
2.0 2.0
8.0 3.0
1.0 4.0
0.0 5.0
9.0 6.0
6.0 7.0
3.0 8.0
4.0 9.0


Regards,

Dave

Footnote: There is a section of this forum called Fortran 90 Programming with NR. I suggest that would be a more appropriate place for Fortran questions.

Ummm...

Isn't that exactly what sort2 is for? ...


Thanks Dave
yeah, it does say that in the book. But how does it use the quick sort algorithm without calling the quicksort algorithm in the first place? I couldnt find anything in either nrutil.f90 or nr.f90.

Should I post this in the other forum first?

Yameng

Edit : I found the two index subroutines further down the chapter, I have to put them in my code right? Or is it already included intrinsically to nr.f90?

Should I post this in the other forum
Well, I'll continue here since we've already started. Maybe a moderator will choose to move this.

If you have other (different) questions about NR with Fortran, I think you should begin a new thread on the Fortran part of the forum.


...I found the two index subroutines further down the chapter...

Since sort2 calls subroutine indexx, you have to compile and link indexx into your the main program.

Look at the indexx subroutine and you can see that it calls subroutines swap and icomp_xchng. The interface definition and source for swap are in nrutil.f90 (along with nrerror and other things that are needed). Source for subroutines indexx and icomp_xchng is in indexx.f90.


But how does it use the quick sort algorithm without calling the quicksort algorithm in the first place?This version of quicksort is based on a Fortran 77 program whose operation is explained here: http://www.nrbook.com/a/bookfpdf/f8-2.pdf
Explicit recursion (a subprogram calling itself) was not supported in versions earlier than Fortran 90.

If you are interested in other non-recursive implementations of quicksort, you can find numerous examples on the web. (You can also find examples of recursive quicksort routines in Fortran 90/95 if you are interested.)



Regards,

Dave