f8-1

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: 322 Chapter8. SortingSample 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).SUBROUTINE piksr2(n,arr,brr) INTEGER n REAL arr(n),brr(n) Sorts an array arr(1:n) into ascending numerical order, by straight insertion, while making the corresponding rearrangement of the array brr(1:n) . INTEGER i,j REAL a,bdo 12j=2,n Pick out each element in turn. a=arr(j) b=brr(j) do11i=j-1,1,-1 Look for the place to insert it. if(arr(i).le.a)goto 10arr(i+1)=arr(i) brr(i+1)=brr(i) enddo 11 i=0 10 arr(i+1)=a Insert it. brr(i+1)=b enddo 12 return END For the case of rearranging a larger number of arrays by sorting on one of them, see §8.4. Shell’s Method Thisisactuallyavariantonstraightinsertion,butaverypowerfulvariantindeed. Theroughidea,e.g.,forthecaseofsorting16numbers n1...n 16,isthis: Firstsort, by straight insertion, each of the 8 groups of 2 (n1,n9),(n2,n10),...,(n8,n16). Next, sort each of the 4 groups of 4 (n1,n5,n9,n13),...,(n4,n8,n12,n16).N e x t sort the 2 groups of 8 records, beginning with (n1,n3,n5,n7,n9,n11,n13,n15). Finally, sort the whole list of 16 numbers. Ofcourse,onlythe lastsortisnecessary forputtingthenumbersintoorder. So what is the purpose of the previous partial sorts? The answer is that the previous sorts allow numbers efficiently to filter up or down to positions close to their final restingplaces. Therefore,thestraightinsertionpassesonthefinalsortrarelyhaveto gopast morethana “few”elementsbeforefindingtherightplace. (Thinkofsortinga hand of cards that are already almost in order.) Thespacingsbetweenthenumberssortedoneachpassthroughthedata(8,4,2,1 in the above example) are called the increments , and a Shell sort is sometimes called adiminishing increment sort . There has been a lot of research into how to choose a good set of increments, but the optimum choice is not known. The set ..., 8,4,2,1is in fact not a good choice, especially for Na power of 2. A much better choice is the sequence (3 k−1)/2,..., 40,13,4,1( 8.1.1 ) which can be generated by the recurrence i1=1 ,i k+1=3 ik+1 ,k =1 ,2,... (8.1.2 ) Itcanbeshown(see [1])thatforthissequenceofincrementsthenumberofoperations required in all is of order N3/2for the worst possible ordering of the original data. 8.2Quicksort 323Sample 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 “randomly” ordered data, the operations count goes approximatelyas N1.25,a t least for N< 60000.F o r N> 50, however, Quicksort is generally faster. The program follows: SUBROUTINE shell(n,a) INTEGER n REAL a(n) Sorts an array a(1:n) into ascending numerical order by Shell’s method (diminishing in- crement sort). nis input; ais replaced on output by its sorted rearrangement. INTEGER i,j,incREAL vinc=1 Determine the starting increment. 1 inc=3*inc+1 if(inc.le.n)goto 1 2 continue Loop over the partial sorts. inc=inc/3 do 11i=inc+1,n Outer loop of straight insertion. v=a(i)j=i 3 if(a(j-inc).gt.v)then Inner loop of straight insertion. a(j)=a(j-inc)j=j-incif(j.le.inc)goto 4 goto 3 endif 4 a(j)=v enddo 11 if(inc.gt.1)goto 2 returnEND CITED REFERENCES AND FURTHER READING: Knuth,D.E. 1973, SortingandSearching ,v ol.3of TheArtofComputerProgramming (Reading, MA: Addison-Wesley),§5.2.1. [1] Sedgewick, R. 1988, Algorithms , 2nd ed. (Reading, MA: Addison-Wesley), Chapter 8. 8.2 Quicksort Quicksort is, on most machines, on average, for large N, the fastest known sorting algorithm. It is a “partition-exchange” sorting method: A “partitioning element” ais selected from the array. Then by pairwise exchangesof elements, the originalarrayispartitionedintotwosubarrays. Attheendofaroundofpartitioning, the element ais in its final place in the array. All elements in the left subarray are ≤a, while all elements in the right subarray are ≥a. The process is then repeated on the left and right subarrays independently, and so on. The partitioning process is carried out by selecting some element, say the leftmost, as the partitioning element a. Scan a pointer up the array until you find an element >a, and then scan another pointer down from the end of the array until you find an element <a. These two elements are clearly out of place for the final partitioned array, so exchange them. Continue this process until the pointers