psmile_quicksort_index.F90

Go to the documentation of this file.
00001 !-----------------------------------------------------------------------
00002 ! Copyright 2006-2010, NEC Europe Ltd., London, UK.
00003 ! All rights reserved. Use is subject to OASIS4 license terms.
00004 !-----------------------------------------------------------------------
00005 !BOP
00006 !
00007 ! !ROUTINE: PSMILe_Quicksort_index
00008 !
00009 ! !INTERFACE:
00010 
00011       subroutine psmile_quicksort_index(a, n, index)
00012 !
00013 ! !USES:
00014 !
00015         use PSMILe, dummy_interface => PSMILe_Quicksort_index
00016 
00017         implicit none
00018 !
00019 ! !INPUT PARAMETERS:
00020 !
00021         integer, intent(In)    :: n
00022 !
00023 ! !INPUT/OUTPUT PARAMETERS:
00024 !
00025         integer, intent(InOut) :: a(n)
00026         integer, intent(InOut) :: index(n)
00027 !
00028 ! !LOCAL VARIABLES
00029 !
00030         integer, Parameter     :: pointer_inc = 64
00031         integer                :: pointer_size
00032         integer, pointer       :: stackl(:), stackr(:)
00033         integer, pointer       :: new_stackl(:), new_stackr(:)
00034 
00035         integer                :: i, j, k, l, r, s
00036         integer                :: ww
00037         integer                :: w, x
00038 !
00039 ! !DESCRIPTION:
00040 !
00041 ! Non-recursive stack version of Quicksort from N. Wirth's Pascal Book,
00042 ! 'Algorithms + Data Structures = Programms'.
00043 !
00044 ! taken from:
00045 !    http://www.nag.com/nagware/examples.asp
00046 !    http://www.nag.com/nagware/Examples/nur.f90
00047 !
00048 ! see also:
00049 !    http://en.wikipedia.org/wiki/Quicksort
00050 !
00051 ! !REVISION HISTORY:
00052 !
00053 !   Date      Programmer   Description
00054 ! ----------  ----------   -----------
00055 ! 19.07.95    Alan Miller  created
00056 ! 13.02.08    R. Redler    revised
00057 !
00058 !----------------------------------------------------------------------
00059 !
00060 !  Initialization
00061 !
00062 #ifdef VERBOSE
00063         print 9990, trim(ch_id)
00064 
00065         call psmile_flushstd
00066 #endif /* VERBOSE */
00067 
00068         pointer_size = pointer_inc
00069 
00070         allocate(new_stackl(pointer_inc), new_stackr(pointer_inc))
00071 
00072         stackl => new_stackl
00073         stackr => new_stackr
00074 
00075         s = 1
00076         stackl(1) = 1
00077         stackr(1) = n
00078         !
00079         !  Start sorting
00080         !        
00081         ! ... keep taking the top request from the stack until s = 0.
00082 
00083 10      continue
00084         l = stackl(s)
00085         r = stackr(s)
00086         s = s - 1
00087 
00088         ! ... keep splitting a(l), ... ,a(r) until l>= r.
00089 
00090 20      continue
00091         i = l
00092         j = r
00093         k = (l+r) / 2
00094         x = a(k)
00095 
00096         ! ... repeat until i > j.
00097 
00098         do
00099            do
00100               if (a(i) < x) then ! Search from lower end
00101                  i = i + 1
00102                  cycle
00103               else
00104                  exit
00105               end if
00106            end do
00107 
00108            do
00109               if (x < a(j)) then ! Search from upper end
00110                  j = j - 1
00111                  cycle
00112               else
00113                  exit
00114               end if
00115            end do
00116 
00117            if (i <= j) then ! Swap positions i & j
00118               w = a(i)
00119               ww = index(i)
00120               a(i) = a(j)
00121               index(i) = index(j)
00122               a(j) = w
00123               index(j) = ww
00124               i = i + 1
00125               j = j - 1
00126               if (i.gt.j) exit
00127            else
00128               exit
00129            end if
00130         end do
00131 
00132         if (j-l >= r-i) then
00133 
00134            if (l < j) then
00135 
00136               if ( s+1 > pointer_size ) then
00137                  pointer_size = pointer_size + pointer_inc
00138                  allocate(new_stackl(pointer_size), new_stackr(pointer_size))
00139                  new_stackl(1:pointer_size-pointer_inc) = &
00140                      stackl(1:pointer_size-pointer_inc)
00141                  new_stackr(1:pointer_size-pointer_inc) = &
00142                      stackr(1:pointer_size-pointer_inc)
00143                  deallocate(stackl, stackr)
00144                  stackl => new_stackl
00145                  stackr => new_stackr
00146               endif
00147 
00148               s = s + 1
00149               stackl(s) = l
00150               stackr(s) = j
00151            end if
00152            l = i
00153 
00154         else
00155 
00156            if (i < r) then
00157 
00158               if ( s+1 > pointer_size ) then
00159                  pointer_size = pointer_size + pointer_inc
00160                  allocate(new_stackl(pointer_size), new_stackr(pointer_size))
00161                  new_stackl(1:pointer_size-pointer_inc) = &
00162                      stackl(1:pointer_size-pointer_inc)
00163                  new_stackr(1:pointer_size-pointer_inc) = &
00164                      stackr(1:pointer_size-pointer_inc)
00165                  deallocate(stackl, stackr)
00166                  stackl => new_stackl
00167                  stackr => new_stackr
00168               endif
00169 
00170               s = s + 1
00171               stackl(s) = i
00172               stackr(s) = r
00173            end if
00174            r = j
00175 
00176         end if
00177 
00178         if (l <  r) GO TO 20
00179         if (s /= 0) GO TO 10
00180 
00181 #ifdef VERBOSE
00182         print 9980, trim(ch_id), pointer_size
00183 
00184         call psmile_flushstd
00185 #endif /* VERBOSE */
00186         !
00187         !  Formats:
00188         !
00189 9990    format (1x, a, ': psmile_quicksort_index')
00190 9980    format (1x, a, ': psmile_quicksort_index: eof, stack size was ', i8)
00191 
00192       end subroutine PSMILe_Quicksort_index

Generated on 18 Mar 2011 for Oasis4 by  doxygen 1.6.1