Sorting 2D arrays into ascending order

[JScot]

Hi Guys,

Basic question for you all - I'm looking for the most efficient way to sort a 2D array into ascending order in terms of only one dimension, e.g. array1(A,B) ---- arrange in ascending order in terms of A.

Does anyone have any suggestions on the quickest way to do this in Fortran 95?

Many thanks.

 

[gummibaer]

There is a multitude of sorting algorithms around. See for instance this link: [URL unfurl="true"]http://en.wikipedia.org/wiki/Sorting_algorithm[/url]

As you can see there, it depends very much on the nature of your problem, which of these algorithms is most suited to your problem.

Norbert

The optimist believes we live in the best of all possible worlds - the pessimist fears this might be true.

 

[xwb]

If your data is nearly ordered, use bubblesort. If it is totally random, try shellsort or quickersort. If you want something with very little thinking, use selection sort.

 

[xwb]

Here is a simple example. Basically there is a list containing the order of the data. The data is not swapped as it could take a long time.

module DataMod
   integer, parameter:: COLMAX = 3
contains
   subroutine DataCreate (out_val, in_size, out_index)
      real, dimension(:,COLMAX), intent (out):: out_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(out):: out_index
      integer:: ii
      real:: val
      
      do ii = 1, in_size
         call random_number (harvest = val)
         val = floor (val * 100.0)
         out_val(ii,1) = val
         out_val(ii,2) = val * val
         out_val(ii,3) = sqrt(val)
      end do

      ! Initialize the indices
      do ix = 1, in_size
         out_index(ix) = ix
      end do
   end subroutine DataCreate
   
   subroutine DataSort (in_val, in_size, out_index)
      real, dimension(:,COLMAX), intent(in):: in_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(out):: out_index(:)
      
      do ix = 1, in_size
         out_index(ix) = ix
      end do
      
      ! Selection sort
      do ii = 1, in_size - 1
         iix = out_index(ii)
         ix = ii
         do jj = ii + 1, in_size
            jix = out_index(jj)
            ! Do your comparison here
            if (in_val(iix,1) .gt. in_val(jix,1)) then
               ! Record the smallest
               ix = jj
               iix = jix
            end if
         end do
         ! Swap
         out_index(ix) = out_index(ii)
         out_index(ii) = iix
      end do
      
   end subroutine DataSort
   
   subroutine DataPrint (in_val, in_size, in_index)
      real, dimension(:,COLMAX), intent (in):: in_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(in):: in_index
      
      ! Show what the order is
      print '(10I4)', (in_index(ii), ii = 1, in_size)
      
      ! Print the data in order
      do ii = 1, in_size
         ix = in_index(ii)
         print '(8F10.2)', (in_val(ix,jj), jj = 1, COLMAX)
      end do
   end subroutine DataPrint
end module DataMod

program main
   use DataMod
   integer, parameter:: VALMAX = 10
   real:: val(VALMAX,COLMAX)
   integer:: index(VALMAX)
   
   call DataCreate (val, VALMAX, index)
   print *, 'Create'
   call DataPrint (val, VALMAX, index)
   
   call DataSort (val, VALMAX, index)
   print *, 'After sorting'
   call DataPrint (val, VALMAX, index)
   stop
end program main

 

[mikrom]

Hi xwb,
Trying to compile your source with gfortran I get these errors:

$ gfortran sort_2D.f95 -o sort_2D
sort_2D.f95:10.30:

      real, dimension(:,COLMAX), intent (out):: out_val
                             1
Error: Bad specification for deferred shape array at (1)
sort_2D.f95:19.9:

         out_val(ii,1) = val
        1
Error: Unclassifiable statement at (1)
sort_2D.f95:20.9:

         out_val(ii,2) = val * val
        1
Error: Unclassifiable statement at (1)
sort_2D.f95:21.9:

         out_val(ii,3) = sqrt(val)
        1
Error: Unclassifiable statement at (1)
sort_2D.f95:31.30:

      real, dimension(:,COLMAX), intent(in):: in_val
                             1
Error: Bad specification for deferred shape array at (1)
sort_2D.f95:60.30:

      real, dimension(:,COLMAX), intent (in):: in_val
                             1
Error: Bad specification for deferred shape array at (1)
sort_2D.f95:76.14:

   use DataMod
             1
Fatal Error: Can't open module file 'datamod.mod' for reading at (1): No such file or directory
gfortran.exe: Internal error: Aborted (program f951)
Please submit a full bug report.
See <[URL unfurl="true"]http://gcc.gnu.org/bugs.html>[/URL] for instructions.

 

[xwb]

Oops! Seems to work on Silverfrost. Anyway, if I don't specify the dimensions, it works with gfortran. Doesn't feel natural but it is slightly faster if I switch the indices of the array round. For 100 items, the following program averages 18ms. When swapped, it averages 12ms.

module DataMod
   integer, parameter:: COLMAX = 3
contains
   subroutine DataCreate (out_val, in_size, out_index)
      real, dimension(:,:), intent (out):: out_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(out):: out_index
      integer:: ii
      real:: val
      
      do ii = 1, in_size
         call random_number (harvest = val)
         val = floor (val * 100.0)
         out_val(ii,1) = val
         out_val(ii,2) = val * val
         out_val(ii,3) = sqrt(val)
      end do

      ! Initialize the indices
      do ix = 1, in_size
         out_index(ix) = ix
      end do
   end subroutine DataCreate
   
   subroutine DataSort (in_val, in_size, out_index)
      real, dimension(:,:), intent(in):: in_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(out):: out_index(:)
      
      do ix = 1, in_size
         out_index(ix) = ix
      end do
      
      ! Selection sort
      do ii = 1, in_size - 1
         iix = out_index(ii)
         ix = ii
         do jj = ii + 1, in_size
            jix = out_index(jj)
            ! Do your comparison here
            if (in_val(iix,1) .gt. in_val(jix,1)) then
               ! Record the smallest
               ix = jj
               iix = jix
            end if
         end do
         ! Swap
         out_index(ix) = out_index(ii)
         out_index(ii) = iix
      end do
      
   end subroutine DataSort
   
   subroutine DataPrint (in_val, in_size, in_index)
      real, dimension(:,:), intent (in):: in_val
      integer, intent(in):: in_size
      integer, dimension(:), intent(in):: in_index
      
      ! Show what the order is
      print '(10I4)', (in_index(ii), ii = 1, in_size)
      
      ! Print the data in order
      do ii = 1, in_size
         ix = in_index(ii)
         print '(8F10.2)', (in_val(ix,jj), jj = 1, COLMAX)
      end do
   end subroutine DataPrint
end module DataMod

program main
   use DataMod
   integer, parameter:: VALMAX = 10
   real:: val(VALMAX,COLMAX)
   integer:: index(VALMAX)
   
   call DataCreate (val, VALMAX, index)
   print *, 'Create'
   call DataPrint (val, VALMAX, index)
   
   call DataSort (val, VALMAX, index)
   print *, 'After sorting'
   call DataPrint (val, VALMAX, index)
   stop
end program main