f8-0

Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).Chapter 8. Sorting 8.0 Introduction Thischapteralmostdoesn’tbelongina bookon numerical methods. However, some practical knowledge of techniques for sorting is an indispensable part of anygoodprogrammer’sexpertise. Wewouldnotwantyoutoconsideryourselfexpertin numerical techniques while remaining ignorant of so basic a subject. In conjunctionwith numericalwork, sorting is frequentlynecessary when data (either experimental or numerically generated) are being handled. One has tables or lists of numbers, representing one or more independent (or “control”) variables, and one or more dependent (or “measured”) variables. One may wish to arrange these data, in various circumstances, in order by one or another of these variables. Alternatively, one may simply wish to identify the “median” value, or the “upperquartile” value of one of the lists of values. This task, closely related to sorting, is called selection. Here, more specifically, are the tasks that this chapter will deal with: Sort, i.e., rearrange, an array of numbers into numerical order. Rearrange an array into numerical order while performing the corre- sponding rearrangement of one or more additional arrays, so that the correspondence between elements in all arrays is maintained. Givenanarray,preparean indextable forit,i.e.,atableofpointerstelling whichnumberarrayelementcomesfirstinnumericalorder,whichsecond, and so on. Given an array, prepare a rank table for it, i.e., a table telling what is the numerical rank of the first array element, the second array element, and so on. Select the Mth largest element from an array. For the basic task of sorting Nelements, the best algorithms require on the order of several times Nlog 2Noperations. The algorithm inventor tries to reduce the constant in front of this estimate to as small a value as possible. Two of thebest algorithms are Quicksort (§8.2), invented by the inimitable C.A.R. Hoare, and Heapsort (§8.3), invented by J.W.J. Williams. Forlarge N(say >1000),Quicksortis faster,onmostmachines,byafactorof 1.5or2;itrequiresabitofextramemory,however,andis amoderatelycomplicated program. Heapsort is a true “sort in place,” and is somewhat more compact toprogram and therefore a bit easier to modify for special purposes. On balance, we recommendQuicksort because of its speed, but we implement both routines. 320 8.1StraightInsertionandShell’sMethod 321Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).For small None does better to use an algorithm whose operation count goes as a higher, i.e., poorer, power of N, if the constant in front is small enough. For N< 20,roughly,the methodof straightinsertion (§8.1)is conciseandfastenough. We include it with some trepidation: It is an N2algorithm, whose potential for misuse (by using it for too large an N) is great. The resultant waste of computer time is so awesome, that we were tempted not to include any N2routine at all. We willdraw the line, however, at the inefficient N2algorithm, beloved of elementary computerscience texts, called bubblesort . If you know what bubble sort is, wipe it from your mind; if you don’t know, make a point of never finding out! For N< 50, roughly, Shell’s method (§8.1),only slightly more complicatedto programthanstraightinsertion,is competitivewith themorecomplicatedQuicksort onmanymachines. Thismethodgoesas N3/2intheworstcase,butisusuallyfaster. See references [1,2]for further information on the subject of sorting, and for detailed references to the literature. CITED REFERENCES AND FURTHER READING: Knuth,D.E. 1973, SortingandSearching ,v ol.3of TheArtofComputerProgramming (Reading, MA: Addison-Wesley). [1] Sedgewick, R. 1988, Algorithms , 2nd ed. (Reading,MA: Addison-Wesley), Chapters 8–13. [2] 8.1 Straight Insertion and Shell’s Method Straight insertion is an N2routine, and should be used only for small N, say <20. The technique is exactly the one used by experiencedcard players to sort their cards: Pick outthesecondcardandputit inorderwith respecttothe first; thenpick out thethird cardandinsert it intothe sequenceamongthe first two; and so onuntil the last card has been picked out and inserted. SUBROUTINE piksrt(n,arr) INTEGER nREAL arr(n) Sorts an array arr(1:n) into ascending numerical order, by straight insertion. nis input; arr is replaced on output by its sorted rearrangement. INTEGER i,j REAL a do12j=2,n Pick out each element in turn. a=arr(j)do 11i=j-1,1,-1 Look for the place to insert it. if(arr(i).le.a)goto 10 arr(i+1)=arr(i) enddo 11 i=0 10 arr(i+1)=a Insert it. enddo 12 return END What if you also want to rearrange an array brrat the same time as you sort arr? Simply movean element of brrwheneveryou movean element of arr: