f8-3

8.3Heapsort 327Sample 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).3 continue Beginning of innermost loop. i=i+1 Scan up to find element >a. if(arr(i).lt.a)goto 3 4 continue j=j-1 Scan down to find element <a. if(arr(j).gt.a)goto 4 if(j.lt.i)goto 5 Pointers crossed. Exit with partitioning complete. temp=arr(i) Exchange elements of both arrays. arr(i)=arr(j) arr(j)=temp temp=brr(i)brr(i)=brr(j)brr(j)=temp goto 3 End of innermost loop. 5 arr(l+1)=arr(j) Insert partitioning element in both arrays. arr(j)=a brr(l+1)=brr(j) brr(j)=bjstack=jstack+2 Push pointers to larger subarray on stack, process smaller subarray immediately. if(jstack.gt.NSTACK)pause ’NSTACK too small in sort2’ if(ir-i+1.ge.j-l)then istack(jstack)=ir istack(jstack-1)=i ir=j-1 else istack(jstack)=j-1 istack(jstack-1)=l l=i endif endif goto 1END You could, in principle, rearrange any number of additional arrays along with brr, but this becomes wasteful as the number of such arrays becomes large. The preferred technique is to make use of an index table, as described in §8.4. CITED REFERENCES AND FURTHER READING: Sedgewick, R. 1978, Communications of the ACM , vol. 21, pp. 847–857. [1] 8.3 Heapsort While usually not quite as fast as Quicksort, Heapsort is one of our favorite sorting routines. It is a true “in-place” sort, requiring no auxiliary storage. It is an Nlog2Nprocess,notonlyonaverage,butalsofortheworst-caseorderofinputdata. Infact, its worst case is only20 percentor so worse thanits averagerunningtime. It is beyondourscope togivea completeexpositiononthe theoryofHeapsort. We will mention the general principles, then let you refer to the references [1,2],o r analyze the program yourself, if you want to understand the details. A set of Nnumbers ai,i =1 ,...,N, is said to form a “heap” if it satisfies the relation aj/2≥ajfor 1≤j/2<j≤N (8.3.1 ) 328 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).a1 a2 a3 a7a6a5 a4 a8a9a10a11a12 Figure 8.3.1. Ordering implied by a “heap,”here of 12 elements. Elements connected by an upward path are sorted with respect to one another, but there is not necessarily any ordering among elements related only “laterally.” Here the division in j/2means“integer divide, ”i.e., is an exact integer or else is roundeddown to the closest integer. De finition (8.3.1)will make sense if you think ofthenumbers aiasbeingarrangedinabinarytree,withthetop, “boss,”nodebeing a1, the two “underling ”nodes being a2and a3,theirfour underlingnodes being a4 through a7,etc. (SeeFigure8.3.1.) Inthisform,aheaphasevery “supervisor ”greater than or equal to its two “supervisees, ”downthroughthe levels of the hierarchy. If you have managed to rearrange your array into an order that forms a heap, then sorting it is very easy: You pull off the “top of the heap, ”which will be the largest element yet unsorted. Then you “promote”to the top of the heap its largest underling. Then you promote itslargest underling, and so on. The process is like what happens (or is supposed to happen) in a large corporation when the chairman oftheboardretires. Youthenrepeatthewholeprocessbyretiringthenewchairmanof the board. Evidently the whole thing is an Nlog 2Nprocess, since each retiring chairman leads to log2Npromotions of underlings. Well, how do you arrange the array into a heap in the first place? The answer is again a “sift-up”process like corporate promotion. Imagine that the corporation startsoutwith N/ 2employeesontheproductionline,butwithnosupervisors. Now a supervisor is hired to supervise two workers. If he is less capable than one of his workers, that one is promoted in his place, and he joins the production line. After supervisors are hired, then supervisors of supervisors are hired, and so on upthe corporate ladder. Each employee is brought in at the top of the tree, but then immediately sifted down, with more capable workers promoted until their proper corporate level has been reached. In the Heapsort implementation, the same “sift-up”code can be used for the initial creation of the heap and for the subsequent retirement-and-promotionphase. One execution of the Heapsort subroutine represents the entire life-cycle of a giant corporation: N/ 2workers are hired; N/ 2potential supervisors are hired; there is a sifting up in the ranks, a sort of super Peter Principle: in due course, each of theoriginal employees gets promoted to chairman of the board. 8.4 IndexingandRanking 329Sample 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 hpsort(n,ra) INTEGER n REAL ra(n) Sorts an array ra(1:n) into ascending numerical order using the Heapsort algorithm. nis input; rais replaced on output by its sorted rearrangement. INTEGER i,ir,j,l REAL rraif (n.lt.2) return The index lwill be decremented from its initial value down to 1 during the “hiring” (heap creation) phase. Once it reaches 1, the index irwill be decremented from its initial value down to 1 during the “retirement-and-promotion” (heap selection) phase. l=n/2+1ir=n 10 continue if(l.gt.1)then Still in hiring phase. l=l-1 rra=ra(l) else In retirement-and-promotion phase. rra=ra(ir) Clear a space at end of array. ra(ir)=ra(1) Retire the top of the heap into it. ir=ir-1 Decrease the size of the corporation. if(ir.eq.1)then Done with the last promotion. ra(1)=rra The least competent worker of all! return endif endifi=l Whether in the hiring phase or promotion phase, we here set up to sift down element rra to its proper level. j=l+l 20 if(j.le.ir)then “Do while j.le.ir :” if(j.lt.ir)then if(ra(j).lt.ra(j+1))j=j+1 Compare to the better underling. endifif(rra.lt.ra(j))then Demote rra. ra(i)=ra(j) i=j j=j+j else This is rra’s level. Set jto terminate the sift-down. j=ir+1 endif goto 20endif ra(i)=rra Put rra into its slot. goto 10END CITED REFERENCES AND FURTHER READING: Knuth,D.E. 1973, SortingandSearching ,v ol.3of TheArtofComputerProgramming (Reading, MA: Addison-Wesley), §5.2.3. [1] Sedgewick, R. 1988, Algorithms , 2nd ed. (Reading, MA: Addison-Wesley), Chapter 11. [2] 8.4 Indexing and Ranking The conceptof keysplays a prominentrole in the managementof data files. A datarecordin sucha file maycontainseveralitems, or fields. Forexample,a record in afile of weather observations may have fields recording time, temperature, and