Follow up Q on sorting. How to quick sort?

[Ahn210]

Hello,

Thanks for answering my prev. question on simple sorting of 2 column data which were:

ID nums
12 0.111
58 1.52
. .
. .
. .
101 0.5
10 2.89

I declared 2 single array ID) and nums)

DO J = 1, 9
DO K = J+1, 10

IF(nums(J) > nums(K)) THEN

temp = nums(K)
temp2 = id(k)
nums(K) = nums(J)
id(k)=id(j)
nums(J) = temp
id(j)=temp2

END IF
END DO
END DO


I know this is very simple method that works with a few rows so I wish to learn Quick sort.
I've tried to understand the quick sort code out there but it is quite hard to comprehend.

Could someone apply quick sort or any other efficient code into my example and highlight the key component?

I really appreciate your help.

 

[mikrom]

Try to use existing source, for example this:

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Fortran

 

[mikrom]

I adapted the code from the link above for your case

...
...
program qsort_test
    use qsort_mod
    implicit none
 
    integer, parameter :: l = 4
    type (group), dimension(l) :: A
    integer :: i

    A(:)%order = (/12, 58, 101, 10/)
    A(:)%value = (/0.111, 1.52, 0.5, 2.89/)

    write (*,*) "Unsorted Values:"
    do i=1, l    
      write (*,"(I5,1X,F8.6))") A(i)%order, A(i)%value
    end do
 
    write(*,*)

    call QSort(A,l)
    write (*,*) "Sorted Values:"
    do i=1, l    
      write (*,"(I5,1X,F8.6))") A(i)%order, A(i)%value
    end do

end program qsort_test

and got the following output:

$ gfortran quicksort.f95 -o quicksort

$ quicksort
 Unsorted Values:
   12 0.111000
   58 1.520000
  101 0.500000
   10 2.890000

 Sorted Values:
   12 0.111000
  101 0.500000
   58 1.520000
   10 2.890000

Is this what you need ?

 

[Ahn210]

To Mikrom

Thanks for the reply! I wish to ask one more question on this.

If I don't know the amount of data.. so I have to use either really big number for loop and dummy parameter OR use allocatable array, how should I set

integer, parameter :: l = 4 ?

I could find total number of data by..

Do
read (12,*,end=1) Rows
nvals=nvals+1
1 End Do


but I can't put

integer, parameter :: l = nvals


since this specification goes before the calculation.

How should I deal with this in case of unknown amount of data?

 

[mikrom]

Use allocatable array and to this:
1. In first loop read the total number of data into nvals
2. allocate your array array with allocate(A(nvals))
3. rewind and in the second loop read the data from the file into array.
See a little example

http://www.tek-tips.com/viewthread.cfm?qid=1564127

 

[Ahn210]

To Mikrom,

I really appreciated your prev. posts. It helped me a lot and I almost figured out except for one minor error.

When I run my code, it reads the input data file and sort.
When I look at my output, along with sorted data, I see some weird number like...

-84215041 -4.316+08
-84215041 -4.316+08
-84215041 -4.316+08
and then I see my data like
10028 0
10044 0.1
20587 0.28
10001 3.54
and so on...

input file on my desktop only contains second part...


Could you check my code???



Module LOAD

Implicit none

type group
integer :: PERMCO ! original order of unsorted data
real :: BV ! values to be sorted by
end type group

contains

Subroutine file2array(fname,array)

character(*),intent(in) :: fname

type(group),allocatable,dimension),intent(in out):: array
type(group) :: rowcount

integer :: i, nr_lines, nr_elements, stat
integer, parameter:: file_in = 11


OPEN (file_in, FILE = fname)

do
read(file_in,*,end=10) rowcount
nr_lines = nr_lines + 1
end do

10 rewind(file_in)

nr_elements = nr_lines

Allocate(array(nr_elements+1))


do i = 1, nr_elements
read(file_in,*,end=11) array(i)%Permco, array(i)%BV

end do

11 rewind(file_in)


close(file_in)

end subroutine file2array

!!!!!!


recursive subroutine QSort(a,na)

! DUMMY ARGUMENTS
integer, intent(in) :: nA
type (group), dimension(nA), intent(in out) :: A

! LOCAL VARIABLES
integer :: left, right
real :: random
real :: pivot
type (group) :: temp
integer :: marker

if (nA > 1) then

call random_number(random)
pivot = A(int(random*real(nA-1))+1)%BV !!!!
! random pivot (not best performance, but avoids worst-case)
left = 0
right = nA + 1

do while (left < right)
right = right - 1
do while (A(right)%BV > pivot)
right = right - 1
end do
left = left + 1
do while (A(left)%BV < pivot)
left = left + 1
end do
if (left < right) then
temp = A(left)
A(left) = A(right)
A(right) = temp
end if
end do

if (left == right) then
marker = left + 1
else
marker = left
end if

call QSort(Amarker-1),marker-1)
call QSort(A(marker,nA-marker+1)

end if

end subroutine QSort




End Module LOAD


!!!!



program Load_qsort_test

USE LOAD
!use qsort_mod
implicit none


!Integer, parameter :: file_out=2

integer number, EOF, LL, i, nvals





TYPE (group),dimension), allocatable:: Arraynew


Call file2array('C:\Users\bahn\Desktop\INPUT00.txt' , Arraynew)

LL = size(arraynew)

call QSort(Arraynew,LL)

DO i= 1,LL
print*, Arraynew(i)%Permco, Arraynew(i)%BV
END DO


pause
end program Load_qsort_test

 

[Ahn210]

oh.. I think I know why...

after removing extra +1 on

Allocate(array(nr_elements+1))

I don't have that issue.

I wanted to be safe by allocating one extra array but maybe it doesn't work like that...

 

[mikrom]

You frgot to initialize nr_lines. Here is the corrected source:

Module LOAD 

Implicit none 

type group 
integer :: PERMCO ! original order of unsorted data 
real :: BV ! values to be sorted by 
end type group 

contains 

Subroutine file2array(fname,array) 

character(*),intent(in) :: fname 

type(group),allocatable,dimension(:),intent(in out):: array 
type(group) :: rowcount 

integer :: i, nr_lines, nr_elements, stat 
integer, parameter:: file_in = 11 


OPEN (file_in, FILE = fname) 

nr_lines = 0
do 
read(file_in,*,end=10) rowcount 
nr_lines = nr_lines + 1 
end do 

10 rewind(file_in) 

nr_elements = nr_lines


Allocate(array(nr_elements)) 


do i = 1, nr_elements 
read(file_in,*) array(i)%Permco, array(i)%BV 

end do 


close(file_in) 

end subroutine file2array 

!!!!!! 


recursive subroutine QSort(a,na) 

! DUMMY ARGUMENTS 
integer, intent(in) :: nA 
type (group), dimension(nA), intent(in out) :: A 

! LOCAL VARIABLES 
integer :: left, right 
real :: random 
real :: pivot 
type (group) :: temp 
integer :: marker 

if (nA > 1) then 

call random_number(random) 
pivot = A(int(random*real(nA-1))+1)%BV !!!! 
! random pivot (not best performance, but avoids worst-case) 
left = 0 
right = nA + 1 

do while (left < right) 
right = right - 1 
do while (A(right)%BV > pivot) 
right = right - 1 
end do 
left = left + 1 
do while (A(left)%BV < pivot) 
left = left + 1 
end do 
if (left < right) then 
temp = A(left) 
A(left) = A(right) 
A(right) = temp 
end if 
end do 

if (left == right) then 
marker = left + 1 
else 
marker = left 
end if 

call QSort(A(:marker-1),marker-1) 
call QSort(A(marker:),nA-marker+1) 

end if 

end subroutine QSort 




End Module LOAD 


!!!! 



program Load_qsort_test 

USE LOAD 
!use qsort_mod 
implicit none 


!Integer, parameter :: file_out=2 

integer number, EOF, LL, i, nvals 





TYPE (group),dimension(:), allocatable:: Arraynew 


Call file2array('INPUT00.txt' , Arraynew) 

LL = size(arraynew) 

call QSort(Arraynew,LL) 

DO i= 1,LL 
print*, Arraynew(i)%Permco, Arraynew(i)%BV 
END DO 

end program Load_qsort_test

 

[mikrom]

When I first tried to run your program with 4 lines of data and printed nr_lines and ll I got the output

 nr_lines =      2491016
 ll =      2491017
       10028   0.0000000    
       10044  0.10000000    
       20587  0.28000000    
       10001   3.5400000    
           0   0.0000000    
           0   0.0000000    
...
...

 

[Ahn210]

Mikrom,

I really learned a lot from you! thank you for pointing the nr_lines = 0 part as well.