Numerical Recipes Forum  

Go Back   Numerical Recipes Forum > Numerical Recipes Third Edition Forum > Methods: All Chapters in NR3

Reply
 
Thread Tools Rate Thread Display Modes
  #1  
Old 07-29-2009, 05:39 AM
TheIsingGuy TheIsingGuy is offline
Registered User
 
Join Date: Jul 2009
Posts: 8
Modification for the quicksort Algorithm

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
Reply With Quote
  #2  
Old 07-29-2009, 11:07 AM
davekw7x davekw7x is offline
Registered User
 
Join Date: Jan 2008
Posts: 453
Quote:
Originally Posted by TheIsingGuy View Post
...
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?

Code:
!
! 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):
Code:
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.

Last edited by davekw7x; 07-29-2009 at 02:37 PM.
Reply With Quote
  #3  
Old 07-30-2009, 05:13 AM
TheIsingGuy TheIsingGuy is offline
Registered User
 
Join Date: Jul 2009
Posts: 8
Quote:
Originally Posted by davekw7x View Post
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?
Reply With Quote
  #4  
Old 07-30-2009, 08:38 AM
davekw7x davekw7x is offline
Registered User
 
Join Date: Jan 2008
Posts: 453
Quote:
Originally Posted by TheIsingGuy
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.


Quote:
Originally Posted by TheIsingGuy
...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.

Quote:
Originally Posted by TheIsingGuy
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
Reply With Quote
Reply

Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 07:15 PM.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.