psmile_quicksort_index.F90
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 subroutine psmile_quicksort_index(a, n, index)
00012
00013
00014
00015 use PSMILe, dummy_interface => PSMILe_Quicksort_index
00016
00017 implicit none
00018
00019
00020
00021 integer, intent(In) :: n
00022
00023
00024
00025 integer, intent(InOut) :: a(n)
00026 integer, intent(InOut) :: index(n)
00027
00028
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
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
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
00080
00081
00082
00083 10 continue
00084 l = stackl(s)
00085 r = stackr(s)
00086 s = s - 1
00087
00088
00089
00090 20 continue
00091 i = l
00092 j = r
00093 k = (l+r) / 2
00094 x = a(k)
00095
00096
00097
00098 do
00099 do
00100 if (a(i) < x) then
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
00110 j = j - 1
00111 cycle
00112 else
00113 exit
00114 end if
00115 end do
00116
00117 if (i <= j) then
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
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