diff options
author | Mohamed Abdelnour <mohamed.k.abdelnour@gmail.com> | 2021-05-30 11:42:05 +0200 |
---|---|---|
committer | David Peter <sharkdp@users.noreply.github.com> | 2021-06-01 22:36:56 +0200 |
commit | b02120cf6679b50bb4e4b2dd9c8e72be5ed4372b (patch) | |
tree | 443c4ca1cce1bc5e967f724061e3b29aec3b9ea6 /tests | |
parent | 702b5caf2d27955da0caf6e4432823b1e7d7fb99 (diff) |
Add Fortran (Fixed Form) syntax test file
Diffstat (limited to 'tests')
3 files changed, 671 insertions, 0 deletions
diff --git a/tests/syntax-tests/highlighted/Fortran (Fixed Form)/quicksort_real_F77.F b/tests/syntax-tests/highlighted/Fortran (Fixed Form)/quicksort_real_F77.F new file mode 100644 index 00000000..1221be86 --- /dev/null +++ b/tests/syntax-tests/highlighted/Fortran (Fixed Form)/quicksort_real_F77.F @@ -0,0 +1,323 @@ +[38;2;117;113;94mC Fortran 77 implementation of a quicksort algorithm for arrays with[0m +[38;2;117;113;94mC real entries.[0m +[38;2;117;113;94mC ----------[0m +[38;2;117;113;94mC June 2019 [0m +[38;2;117;113;94mC Jason Allen Anema, Ph.D.[0m +[38;2;117;113;94mC Division of Statistical Genomics[0m +[38;2;117;113;94mC Department of Genetics[0m +[38;2;117;113;94mC Washington University School of Medicine in St. Louis[0m +[38;2;117;113;94mC [0m +[38;2;117;113;94mC This work is partially supported NIH grant AG023746[0m +[38;2;117;113;94mC ----------[0m +[38;2;117;113;94mC Insertion sort is used for short arrays, as quicksort is slower on[0m +[38;2;117;113;94mC these.[0m +[38;2;117;113;94mC [0m +[38;2;117;113;94mC Hoare partition scheme is used (sweeping left and right), as it does[0m +[38;2;117;113;94mC three times fewer swaps on average that the Lamuto partition scheme.[0m +[38;2;117;113;94mC In conjunction with this, tripartite partition is performed[0m +[38;2;117;113;94mC concurrently (solving the "Dutch National Flag problem"). This avoids [0m +[38;2;117;113;94mC horrible runtimes on highly repetitive arrays. For example, without [0m +[38;2;117;113;94mC this, an array of random zeros and ones would have a runtime of[0m +[38;2;117;113;94mC O(N^2), but now has a runtime of O(N). The runtime for this algorthm[0m +[38;2;117;113;94mC on arrays with k highly repetitive entries is now O(kN).[0m +[38;2;117;113;94mC [0m +[38;2;117;113;94mC For medium length (sub)arrays, pivots are choosen using[0m +[38;2;117;113;94mC Median-of-Three, and those three items are sorted. For longer (sub)arrays[0m +[38;2;117;113;94mC the pseudomedian of nine (Median of medians). This avoids O(N^2) runtime on[0m +[38;2;117;113;94mC nonrandom inputs such as increasing and decreasing sequences. [0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC See Louis Bentley, Jon & McIlroy, Douglas. (1993). Engineering a Sort Function.[0m +[38;2;117;113;94mC Softw., Pract. Exper.. 23. 1249-1265. 10.1002/spe.4380231105 for details. [0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC The ordering on elements of the array are defined by a comparison[0m +[38;2;117;113;94mC function,compar, that is a user-supplied INTEGER*2 function of the form[0m +[38;2;117;113;94mC compar(a,b) which returns:[0m +[38;2;117;113;94mC -1 if a precedes b[0m +[38;2;117;113;94mC +1 if b precedes a[0m +[38;2;117;113;94mC 0 is a and b are considered equivalent[0m +[38;2;117;113;94mC and thus defines a total ordering.[0m +[38;2;117;113;94mC [0m +[38;2;117;113;94mC If one would like to use the standard order on integers, the[0m +[38;2;117;113;94mC compar function could be written in a file "compint.F" as:[0m +[38;2;117;113;94mC ----------------------------------------------------------------[0m +[38;2;117;113;94mC INTEGER*2 FUNCTION compint(a,b)[0m +[38;2;117;113;94mC INTEGER a, b[0m +[38;2;117;113;94mC if(a.lt.b)then[0m +[38;2;117;113;94mC compint = -1[0m +[38;2;117;113;94mC elseif(a.gt.b)then[0m +[38;2;117;113;94mC compint = +1[0m +[38;2;117;113;94mC else[0m +[38;2;117;113;94mC compint = 0[0m +[38;2;117;113;94mC endif[0m +[38;2;117;113;94mC END[0m +[38;2;117;113;94mC ----------------------------------------------------------------[0m +[38;2;117;113;94mC Then in your program, call quicksort with:[0m +[38;2;117;113;94mC call quicksort_real_F77(array, n, compint)[0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC The maximal length of an array in this implementation is (2^31-1),[0m +[38;2;117;113;94mC but can be changed to allow for length up to (2^63-1) by changing the[0m +[38;2;117;113;94mC data types of the relevant variables and constants. If you wish to [0m +[38;2;117;113;94mC sort longer arrays, of length N, you'll need to customize variable [0m +[38;2;117;113;94mC and constant types and set mstack to be at least (2*log_2(N)+2). [0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC ----------------------------------------------------------------[0m +[38;2;117;113;94mC Copyright 2019 Jason Allen Anema[0m +[38;2;117;113;94mC [0m +[38;2;117;113;94mC Permission is hereby granted, free of charge, to any person obtaining[0m +[38;2;117;113;94mC a copy of this software and associated documentation files (the "Software"),[0m +[38;2;117;113;94mC to deal in the Software without restriction, including without limitation the[0m +[38;2;117;113;94mC rights to use, copy, modify, merge, publish, distribute, sublicense, and/or[0m +[38;2;117;113;94mC sell copies of the Software, and to permit persons to whom the Software is[0m +[38;2;117;113;94mC furnished to do so, subject to the following conditions:[0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC The above copyright notice and this permission notice shall be included[0m +[38;2;117;113;94mC in all copies or substantial portions of the Software.[0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS[0m +[38;2;117;113;94mC OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,[0m +[38;2;117;113;94mC FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL[0m +[38;2;117;113;94mC THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER[0m +[38;2;117;113;94mC LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING[0m +[38;2;117;113;94mC FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS[0m +[38;2;117;113;94mC IN THE SOFTWARE.[0m +[38;2;117;113;94mC -------------------------------------------------------------------[0m +[38;2;117;113;94mC[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mSUBROUTINE[0m[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_real_F77[0m[38;2;248;248;242m([0m[3;38;2;253;151;31marray[0m[38;2;248;248;242m,[0m[3;38;2;253;151;31mn[0m[38;2;248;248;242m,[0m[3;38;2;253;151;31mcompar[0m[38;2;248;248;242m)[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mINTEGER[0m[38;2;248;248;242m n, maxins, maxmid, mstack[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mREAL[0m[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(n)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mPARAMETER[0m[38;2;248;248;242m (maxins[0m[38;2;249;38;114m = [0m[38;2;190;132;255m7[0m[38;2;248;248;242m, maxmid[0m[38;2;249;38;114m = [0m[38;2;190;132;255m40[0m[38;2;248;248;242m, mstack[0m[38;2;249;38;114m = [0m[38;2;190;132;255m128[0m[38;2;248;248;242m)[0m +[38;2;117;113;94mC maxins: maximal size of (sub)arrays to be sorted with[0m +[38;2;117;113;94mC insertion sort.[0m +[38;2;117;113;94mC maxmid: maximal size of (sub)arrays that will be quicksorted with[0m +[38;2;117;113;94mC Median-of-Three pivots.[0m +[38;2;117;113;94mC mstack: maximal size of required auxiliary storage (a stack), plus 2 [0m +[38;2;117;113;94mC extra spots, which tracks the starts and ends of yet unsorted [0m +[38;2;117;113;94mC subarrays. mstack = 130 is large enough to handle arrays up to [0m +[38;2;117;113;94mC length 2^63-1. This maximal size follows from[0m +[38;2;117;113;94mC processing smaller arrays first and pigeonhole principal.[0m +[38;2;117;113;94mC [0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mINTEGER[0m[38;2;248;248;242m a, d, i, j, k, s, lo, mid, hi, tstack, [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(mstack)[0m +[38;2;117;113;94mC a, d, i, j, k, s: indices[0m +[38;2;117;113;94mC lo, mid, and hi: their natural location in a (sub)array[0m +[38;2;117;113;94mC tstack: equal to twice the number of additional subarrays still [0m +[38;2;117;113;94mC needing to be sorted[0m +[38;2;117;113;94mC bstack: stack of the endpoints of unsorted subarrays[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mINTEGER[0m[38;2;248;248;242m pm1, pm2, pm3, pm4, pm5, pm6, pm7, pm8, pm9[0m +[38;2;117;113;94mC for pseudomedian of nine positions in (sub)arrays[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mREAL[0m[38;2;248;248;242m piv, temp[0m +[38;2;117;113;94mC piv is to store the pivot's value[0m +[38;2;117;113;94mC [0m +[38;2;248;248;242m [0m[38;2;249;38;114mEXTERNAL[0m[38;2;248;248;242m compar[0m +[38;2;248;248;242m [0m[3;38;2;102;217;239mINTEGER[0m[38;2;249;38;114m*[0m[38;2;190;132;255m2[0m[38;2;248;248;242m compar[0m +[38;2;117;113;94mC compar is a user-supplied INTEGER*2 function of the form[0m +[38;2;117;113;94mC compar(a,b) which returns:[0m +[38;2;117;113;94mC -1 if a precedes b[0m +[38;2;117;113;94mC +1 if b precedes a[0m +[38;2;117;113;94mC 0 is a and b are considered equivalent[0m +[38;2;117;113;94mC and thus defines a total ordering. [0m +[38;2;248;248;242m tstack[0m[38;2;249;38;114m = [0m[38;2;190;132;255m0[0m +[38;2;248;248;242m lo[0m[38;2;249;38;114m = [0m[38;2;190;132;255m1[0m[38;2;248;248;242m [0m +[38;2;248;248;242m hi[0m[38;2;249;38;114m = [0m[38;2;248;248;242mn[0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC Insertion sort subarrays of size maxins or less[0m +[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1.[0m[38;2;248;248;242mle.maxins)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m [0m[38;2;249;38;114mdo[0m[38;2;248;248;242m [0m[38;2;190;132;255m10[0m[38;2;248;248;242m, i[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m, hi, 1[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mdo[0m[3;38;2;253;151;31m 11 [0m[38;2;248;248;242mj[0m[38;2;249;38;114m = [0m[38;2;248;248;242mi [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m, lo, [0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j), temp)[0m[38;2;249;38;114m.le.[0m[38;2;190;132;255m0[0m[38;2;248;248;242m)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m2[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114m=[0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j)[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m11[0m[38;2;248;248;242m [0m[38;2;249;38;114mcontinue[0m +[38;2;248;248;242m j[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m +[38;2;248;248;242m [0m[38;2;190;132;255m2[0m[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m10[0m[38;2;248;248;242m [0m[38;2;249;38;114mcontinue[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(tstack[0m[38;2;249;38;114m.eq.[0m[38;2;190;132;255m0[0m[38;2;248;248;242m)[0m[38;2;249;38;114mreturn[0m +[38;2;117;113;94mC Pop the bstack, and start new partitioning[0m +[38;2;248;248;242m hi[0m[38;2;249;38;114m = [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack)[0m +[38;2;248;248;242m lo[0m[38;2;249;38;114m = [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m +[38;2;248;248;242m tstack[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtstack [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m2[0m +[38;2;248;248;242m [0m[38;2;249;38;114melse[0m +[38;2;117;113;94mC Use Median-of-Three as choice of pivot (median of lo, middle, hi)[0m +[38;2;117;113;94mC and reorder those elements appropriately when subarrays are medium[0m +[38;2;117;113;94mC length (between maxins and maxmid)[0m +[38;2;248;248;242m mid[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo[0m[38;2;249;38;114m.le.[0m[38;2;248;248;242mmaxmid)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Use pseudomedian of nine (Median of medians) as choice of pivot when [0m +[38;2;117;113;94mC subarrays are longer than maxmid. Note that doing it this way requires only 12[0m +[38;2;117;113;94mC comparisons for finding the pivot.[0m +[38;2;248;248;242m [0m[38;2;249;38;114melseif[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1.[0m[38;2;248;248;242mgt.maxmid)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m pm1[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo[0m +[38;2;248;248;242m pm5[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm9[0m[38;2;249;38;114m = [0m[38;2;248;248;242mhi[0m +[38;2;248;248;242m pm3[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (pm5[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm7[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpm5 [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mpm5)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm2[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (pm3[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm4[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpm3 [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (pm5[0m[38;2;249;38;114m-[0m[38;2;248;248;242mpm3)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm6[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpm5 [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (pm7[0m[38;2;249;38;114m-[0m[38;2;248;248;242mpm5)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;248;248;242m pm8[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpm7 [0m[38;2;249;38;114m+[0m[38;2;248;248;242m (pm9[0m[38;2;249;38;114m-[0m[38;2;248;248;242mpm7)[0m[38;2;249;38;114m/[0m[38;2;190;132;255m2[0m +[38;2;117;113;94mC Median and sorting for pm1, pm2, pm3[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm1)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm3)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Median and sorting for pm4, pm5, pm6[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm4)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm6)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Median and sorting for pm7, pm8, pm9[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm7)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm9)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Median of the medians (which are now pm2, pm5, pm8)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm2)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8), [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5))[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm8)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(pm5)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Pivot assigned for medium and long length subarrays.[0m +[38;2;117;113;94mC Note that pm5 = mid[0m +[38;2;248;248;242m piv[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(mid)[0m +[38;2;117;113;94mC Initialize pointers for partitioning[0m +[38;2;248;248;242m i[0m[38;2;249;38;114m = [0m[38;2;248;248;242mlo[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m +[38;2;248;248;242m j[0m[38;2;249;38;114m = [0m[38;2;248;248;242mhi[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m +[38;2;117;113;94mC Initialize counts of repeat values of pivot.[0m +[38;2;248;248;242m a[0m[38;2;249;38;114m = [0m[38;2;190;132;255m0[0m +[38;2;248;248;242m d[0m[38;2;249;38;114m = [0m[38;2;190;132;255m0[0m +[38;2;117;113;94mC Beginning of outer loop for placing pivot.[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m3[0m[38;2;248;248;242m [0m[38;2;249;38;114mcontinue[0m +[38;2;117;113;94mC Scan up to find an element > piv.[0m +[38;2;248;248;242m i[0m[38;2;249;38;114m = [0m[38;2;248;248;242mi [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m +[38;2;117;113;94mC Check if pointers crossed.[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m.lt.[0m[38;2;248;248;242mi)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m5[0m +[38;2;117;113;94mC Check if i pointer hit hi boundary.[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(i[0m[38;2;249;38;114m.eq.[0m[38;2;248;248;242mhi)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m4[0m +[38;2;117;113;94mC [0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i), piv)[0m[38;2;249;38;114m.eq.[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m3[0m +[38;2;117;113;94mC Check for copies of pivot from scanning right. [0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i), piv)[0m[38;2;249;38;114m.eq.[0m[38;2;190;132;255m0[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo[0m[38;2;249;38;114m+[0m[38;2;248;248;242ma)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo[0m[38;2;249;38;114m+[0m[38;2;248;248;242ma)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpiv[0m +[38;2;248;248;242m a[0m[38;2;249;38;114m = [0m[38;2;248;248;242ma [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m +[38;2;248;248;242m [0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m3[0m[38;2;248;248;242m [0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Beginning of innerloop for placing pivot.[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m4[0m[38;2;248;248;242m [0m[38;2;249;38;114mcontinue[0m +[38;2;117;113;94mC Scan down to find an element < piv.[0m +[38;2;248;248;242m j[0m[38;2;249;38;114m = [0m[38;2;248;248;242mj [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m +[38;2;117;113;94mC Check if pointers crossed.[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m.lt.[0m[38;2;248;248;242mi)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m5[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j), piv)[0m[38;2;249;38;114m.eq.[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m4[0m +[38;2;117;113;94mC Check for copies of pivot from scanning left. [0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m([0m[38;2;248;248;242mcompar[0m[38;2;248;248;242m([0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j), piv)[0m[38;2;249;38;114m.eq.[0m[38;2;190;132;255m0[0m[38;2;248;248;242m)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242md)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242md)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpiv[0m +[38;2;248;248;242m d[0m[38;2;249;38;114m = [0m[38;2;248;248;242md [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m +[38;2;248;248;242m [0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m4[0m[38;2;248;248;242m [0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC Check if pointers crossed.[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m.lt.[0m[38;2;248;248;242mi)[0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m5[0m +[38;2;117;113;94mC Exchange elements[0m +[38;2;248;248;242m temp[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtemp[0m +[38;2;117;113;94mC End of outermost loop for placing pivot.[0m +[38;2;248;248;242m [0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m3[0m +[38;2;117;113;94mC Insert all copies of pivot in appropriate place[0m +[38;2;248;248;242m [0m[38;2;190;132;255m5[0m[38;2;248;248;242m s[0m[38;2;249;38;114m = [0m[38;2;102;217;239mMIN[0m[38;2;248;248;242m(a, j[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo[0m[38;2;249;38;114m-[0m[38;2;248;248;242ma[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mDO[0m[3;38;2;253;151;31m 6 [0m[38;2;248;248;242mk[0m[38;2;249;38;114m = [0m[38;2;190;132;255m1[0m[38;2;248;248;242m, s[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(lo[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;249;38;114m+[0m[38;2;248;248;242mk)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i[0m[38;2;249;38;114m-[0m[38;2;248;248;242mk)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(i[0m[38;2;249;38;114m-[0m[38;2;248;248;242mk)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpiv[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m6[0m[38;2;248;248;242m [0m[38;2;249;38;114mCONTINUE[0m +[38;2;248;248;242m s[0m[38;2;249;38;114m = [0m[38;2;102;217;239mMIN[0m[38;2;248;248;242m(d, hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mj[0m[38;2;249;38;114m-[0m[38;2;248;248;242md)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mDO[0m[3;38;2;253;151;31m 7 [0m[38;2;248;248;242mk[0m[38;2;249;38;114m = [0m[38;2;190;132;255m1[0m[38;2;248;248;242m, s[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;249;38;114m-[0m[38;2;248;248;242mk)[0m[38;2;249;38;114m = [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;248;248;242mk)[0m +[38;2;248;248;242m [0m[38;2;248;248;242marray[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;248;248;242mk)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mpiv[0m +[38;2;248;248;242m [0m[3;38;2;253;151;31m7[0m[38;2;248;248;242m [0m[38;2;249;38;114mCONTINUE[0m +[38;2;117;113;94mC Increase effective stack size[0m +[38;2;248;248;242m tstack[0m[38;2;249;38;114m = [0m[38;2;248;248;242mtstack [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m2[0m[38;2;248;248;242m [0m +[38;2;117;113;94mC Push pointers to larger subarray on stack for later processing,[0m +[38;2;117;113;94mC process smaller subarray immediately. [0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(tstack[0m[38;2;249;38;114m.gt.[0m[38;2;248;248;242mmstack) [0m[38;2;249;38;114mTHEN[0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'Stack size is too small in quicksort fortran code quicksort_real_F77.F'[0m[38;2;248;248;242m [0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'Are you sure you want to sort an array this long?'[0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'Your array has more than 2^63-1 entries?'[0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'If so, set mstack parameter to be at least:'[0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'2*ceiling(log_2(N))+2, for N = length of array,'[0m +[38;2;248;248;242m [0m[38;2;102;217;239mWRITE[0m[38;2;248;248;242m([0m[38;2;249;38;114m*[0m[38;2;248;248;242m,[0m[38;2;249;38;114m*[0m[38;2;248;248;242m)[0m[38;2;230;219;116m'and recompile this subroutine.'[0m +[38;2;248;248;242m [0m[38;2;249;38;114mRETURN[0m[38;2;248;248;242m [0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m(hi[0m[38;2;249;38;114m-[0m[38;2;248;248;242mj[0m[38;2;249;38;114m-[0m[38;2;248;248;242md[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1.[0m[38;2;248;248;242mge.j[0m[38;2;249;38;114m-[0m[38;2;248;248;242ma[0m[38;2;249;38;114m-[0m[38;2;248;248;242mlo)[0m[38;2;249;38;114mthen[0m +[38;2;248;248;242m [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack)[0m[38;2;249;38;114m = [0m[38;2;248;248;242mhi[0m +[38;2;248;248;242m [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114m = [0m[38;2;102;217;239mMIN[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;248;248;242md[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;248;248;242m, hi)[0m +[38;2;248;248;242m hi[0m[38;2;249;38;114m=[0m[38;2;102;217;239mMAX[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m-[0m[38;2;248;248;242ma,lo)[0m +[38;2;248;248;242m [0m[38;2;249;38;114melse[0m +[38;2;248;248;242m [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack)[0m[38;2;249;38;114m=[0m[38;2;102;217;239mMAX[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m-[0m[38;2;248;248;242ma,lo)[0m +[38;2;248;248;242m [0m[38;2;248;248;242mbstack[0m[38;2;248;248;242m(tstack[0m[38;2;249;38;114m-[0m[38;2;190;132;255m1[0m[38;2;248;248;242m)[0m[38;2;249;38;114m=[0m[38;2;248;248;242mlo[0m +[38;2;248;248;242m lo[0m[38;2;249;38;114m=[0m[38;2;102;217;239mMIN[0m[38;2;248;248;242m(j[0m[38;2;249;38;114m+[0m[38;2;248;248;242md[0m[38;2;249;38;114m+[0m[38;2;190;132;255m1[0m[38;2;248;248;242m,hi)[0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;117;113;94mC[0m +[38;2;117;113;94mC end of outermost if statement [0m +[38;2;248;248;242m [0m[38;2;249;38;114mendif[0m +[38;2;248;248;242m [0m[38;2;249;38;114mgoto[0m[38;2;248;248;242m [0m[3;38;2;253;151;31m1[0m +[38;2;117;113;94mC END of subroutine quicksort[0m +[38;2;248;248;242m [0m[38;2;249;38;114mEND[0m diff --git a/tests/syntax-tests/source/Fortran (Fixed Form)/LICENSE.md b/tests/syntax-tests/source/Fortran (Fixed Form)/LICENSE.md new file mode 100644 index 00000000..4281fe35 --- /dev/null +++ b/tests/syntax-tests/source/Fortran (Fixed Form)/LICENSE.md @@ -0,0 +1,25 @@ +The `quicksort_real_F77.F` file has been added from https://github.com/jasonanema/Quicksort_Fortran77 under the following license: + +```text +MIT License + +Copyright (c) 2019 Jason Anema + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +``` diff --git a/tests/syntax-tests/source/Fortran (Fixed Form)/quicksort_real_F77.F b/tests/syntax-tests/source/Fortran (Fixed Form)/quicksort_real_F77.F new file mode 100644 index 00000000..6868c4cd --- /dev/null +++ b/tests/syntax-tests/source/Fortran (Fixed Form)/quicksort_real_F77.F @@ -0,0 +1,323 @@ +C Fortran 77 implementation of a quicksort algorithm for arrays with +C real entries. +C ---------- +C June 2019 +C Jason Allen Anema, Ph.D. +C Division of Statistical Genomics +C Department of Genetics +C Washington University School of Medicine in St. Louis +C +C This work is partially supported NIH grant AG023746 +C ---------- +C Insertion sort is used for short arrays, as quicksort is slower on +C these. +C +C Hoare partition scheme is used (sweeping left and right), as it does +C three times fewer swaps on average that the Lamuto partition scheme. +C In conjunction with this, tripartite partition is performed +C concurrently (solving the "Dutch National Flag problem"). This avoids +C horrible runtimes on highly repetitive arrays. For example, without +C this, an array of random zeros and ones would have a runtime of +C O(N^2), but now has a runtime of O(N). The runtime for this algorthm +C on arrays with k highly repetitive entries is now O(kN). +C +C For medium length (sub)arrays, pivots are choosen using +C Median-of-Three, and those three items are sorted. For longer (sub)arrays +C the pseudomedian of nine (Median of medians). This avoids O(N^2) runtime on +C nonrandom inputs such as increasing and decreasing sequences. +C +C See Louis Bentley, Jon & McIlroy, Douglas. (1993). Engineering a Sort Function. +C Softw., Pract. Exper.. 23. 1249-1265. 10.1002/spe.4380231105 for details. +C +C The ordering on elements of the array are defined by a comparison +C function,compar, that is a user-supplied INTEGER*2 function of the form +C compar(a,b) which returns: +C -1 if a precedes b +C +1 if b precedes a +C 0 is a and b are considered equivalent +C and thus defines a total ordering. +C +C If one would like to use the standard order on integers, the +C compar function could be written in a file "compint.F" as: +C ---------------------------------------------------------------- +C INTEGER*2 FUNCTION compint(a,b) +C INTEGER a, b +C if(a.lt.b)then +C compint = -1 +C elseif(a.gt.b)then +C compint = +1 +C else +C compint = 0 +C endif +C END +C ---------------------------------------------------------------- +C Then in your program, call quicksort with: +C call quicksort_real_F77(array, n, compint) +C +C The maximal length of an array in this implementation is (2^31-1), +C but can be changed to allow for length up to (2^63-1) by changing the +C data types of the relevant variables and constants. If you wish to +C sort longer arrays, of length N, you'll need to customize variable +C and constant types and set mstack to be at least (2*log_2(N)+2). +C +C ---------------------------------------------------------------- +C Copyright 2019 Jason Allen Anema +C +C Permission is hereby granted, free of charge, to any person obtaining +C a copy of this software and associated documentation files (the "Software"), +C to deal in the Software without restriction, including without limitation the +C rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +C sell copies of the Software, and to permit persons to whom the Software is +C furnished to do so, subject to the following conditions: +C +C The above copyright notice and this permission notice shall be included +C in all copies or substantial portions of the Software. +C +C THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF AN |