336 Chapter 8.Sorting 22 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 88.4. CITED REFERENCES AND FURTHER READING: Sedgewick,R.1978,Communications of the ACM,vol.21,pp.847-857.[1] NUMERICAL 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 N log2 N process,not only on average,but also for the worst-case order of input data In fact,its worst case is only 20 percent or so worse than its average running time. 3②州 Press. 需 It is beyond our scope to give a complete exposition on the theory of Heapsort. We will mention the general principles,then let you refer to the references [1.21,or analyze the program yourself,if you want to understand the details. A set of N numbers ai,i=1,...,N,is said to form a "heap"if it satisfies the relation a/2≥aj for1≤j/2<j≤N (8.3.1) 61 Here the division in j/2 means "integer divide,"ie.,is an exact integer or else is rounded down to the closest integer.Definition(8.3.1)will make sense if you think of the numbers a;as being arranged in a binary tree,with the top,"boss,"node being a1,the two "underling"nodes being a2 and a3,their four underling nodes being a4 、三 througha7,etc.(See Figure 8.3.1.)In this form,a heap has every"supervisor"greater Numerica 10521 than or equal to its two"supervisees,"down through the levels of the hierarchy. 431 If you have managed to rearrange your array into an order that forms a heap, E Recipes 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 its largest underling,and so on.The process is like North what happens(or is supposed to happen)in a large corporation when the chairman of the board retires.You then repeat the whole process by retiring the new chairman of the board.Evidently the whole thing is an N log2 N process,since each retiring chairman leads to log2 N promotions 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 starts out with N/2 employees on the production line,but with no supervisors.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 up
336 Chapter 8. Sorting Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). } } } 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 N log2 N process, not only on average, but also for the worst-case order of input data. In fact, its worst case is only 20 percent or so worse than its average running time. It is beyond our scope to give a complete exposition on the theory of Heapsort. We will mention the general principles, then let you refer to the references [1,2], or analyze the program yourself, if you want to understand the details. A set of N numbers ai, i = 1,...,N, is said to form a “heap” if it satisfies the relation aj/2 ≥ aj for 1 ≤ j/2 < j ≤ N (8.3.1) Here the division in j/2 means “integer divide,” i.e., is an exact integer or else is rounded down to the closest integer. Definition (8.3.1) will make sense if you think of the numbers ai as being arranged in a binary tree, with the top, “boss,” node being a1, the two “underling” nodes being a2 and a3, their four underling nodes being a4 through a7, etc. (See Figure 8.3.1.) In this form, a heap has every “supervisor” greater than or equal to its two “supervisees,” down through the 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 its largest underling, and so on. The process is like what happens (or is supposed to happen) in a large corporation when the chairman of the board retires. You then repeat the whole process by retiring the new chairman of the board. Evidently the whole thing is an N log 2 N process, since each retiring chairman leads to log2 N promotions 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 starts out with N/2 employees on the production line, but with no supervisors. 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 up
8.3 Heapsort 337 01 as 6 http://www.nr. 83 d10 a12 鱼 18881892 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 1-600 related only "laterally." from NUMERICAL RECIPESI the corporate ladder.Each employee is brought in at the top of the tree,but then 6 immediately sifted down,with more capable workers promoted until their proper corporate level has been reached. (Nort server 9 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-promotion phase. Ameri computer One execution of the Heapsort function represents the entire life-cycle of a giant ART corporation:N/2 workers are hired;N/2 potential supervisors are hired;there is a 9 Program sifting up in the ranks,a sort of super Peter Principle:in due course,each of the original employees gets promoted to chairman of the board. void hpsort(unsigned long n,float ra]) Sorts an array ra[1..n]into ascending numerical order using the Heapsort algorithm.n is input;ra is replaced on output by its sorted rearrangement. unsigned long i,ir,j,1; float rra; 1788-1982 OF SCIENTIFIC COMPUTING(ISBN if (n 2)return; 1=(n>>1)+1; 12-521 1r=n; The index 1 will be decremented from its initial value down to 1 during the "hiring"(heap creation)phase.Once it reaches 1,the index ir will be decremented from its initial value Numerical Recipes 43108 down to 1 during the "retirement-and-promotion"(heap selection)phase. for(;;)[ 1f(1>1)[ Still in hiring phase. (outside rrasra[--1]; Software. else In retirement-and-promotion phase. North rra=rafir]; Clear a space at end of array. ra[ir]-ra[1]; Retire the top of the heap into it Amer 1f(--1r==1)[ Done with the last promotion. ra[i]=rra; The least competent worker of all! break; 11; Whether in the hiring phase or promotion phase,we j=1+1; here set up to sift down element rra to its proper while (j <ir){ evel if (i<ir &ra[i]ra[j+1])++; Compare to the better underling. if (rra ra[j]){ Demote rra. ra[i]=ra[j];
8.3 Heapsort 337 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). a1 a2 a3 a7 a6 a5 a4 a8 a9 a10 a11 a12 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.” the 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-promotion phase. One execution of the Heapsort function represents the entire life-cycle of a giant corporation: N/2 workers are hired; N/2 potential supervisors are hired; there is a sifting up in the ranks, a sort of super Peter Principle: in due course, each of the original employees gets promoted to chairman of the board. void hpsort(unsigned long n, float ra[]) Sorts an array ra[1..n] into ascending numerical order using the Heapsort algorithm. n is input; ra is replaced on output by its sorted rearrangement. { unsigned long i,ir,j,l; float rra; if (n > 1)+1; ir=n; The index l will be decremented from its initial value down to 1 during the “hiring” (heap creation) phase. Once it reaches 1, the index ir will be decremented from its initial value down to 1 during the “retirement-and-promotion” (heap selection) phase. for (;;) { if (l > 1) { Still in hiring phase. 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. if (--ir == 1) { Done with the last promotion. ra[1]=rra; The least competent worker of all! break; } } i=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; while (j <= ir) { if (j < ir && ra[j] < ra[j+1]) j++; Compare to the better underling. if (rra < ra[j]) { Demote rra. ra[i]=ra[j];
338 Chapter 8.Sorting 1=j; j<<=1; else break; Found rra's level.Terminate the sift-down. ra[i]=rra; Put rra into its slot. 2 CITED REFERENCES AND FURTHER READING: Knuth,D.E.1973,Sorting and Searching,vol.3 of The Art of Computer Programming(Reading. MA:Addison-Wesley),$5.2.3.[1] Sedgewick,R.1988,A/lgorithms,2nd ed.(Reading,MA:Addison-Wesley),Chapter 11.[2] nted for 8.4 Indexing and Ranking The concept of keys plays a prominent role in the management of data files.A data record in such a file may contain several items,or fields.For example,a record in a file of weather observations may have fields recording time,temperature,and 三￥2 令 wind velocity.When we sort the records,we must decide which of these fields we want to be brought into sorted order.The other fields in a record just come along for the ride,and will not,in general,end up in any particular order.The field on which the sort is performed is called the key field. For a data file with many records and many fields,the actual movement of N records into the sorted order of their keys Ki,i=1,...,N,can be a daunting task. Instead,one can construct an index table Ij,j=1,...,N,such that the smallest Ki has i=11,the second smallest has i=12,and so on up to the largest Ki with i=IN.In other words,the array K1,j=1,2,,W (8.4.1) is in sorted order when indexed by j.When an index table is available,one need not move records from their original order.Further,different index tables can be made from the same set of records,indexing them to different keys. Numerica 10.621 The algorithm for constructing an index table is straightforward:Initialize the index array with the integers from I to N,then perform the Quicksort algorithm, 431 moving the elements around as ifone were sorting the keys.The integer that initially numbered the smallest key thus ends up in the number one position,and so on. (outside Recipes Software. #include "nrutil.h" #define SWAP(a,b)itemp=(a);(a)=(b);(b)=itemp; #define M 7 #define NSTACK 50 void indexx(unsigned long n,float arr[],unsigned long indx[]) Indexes an array arr[1..n],i.e.,outputs the array indx[1..n]such that arr [indx[j]]is in ascending order for j=1,2,...,N.The input quantities n and arr are not changed. unsigned long i,indxt,ir=n,itemp,j,k,1=1; int jstack=0,*istack; float a; istack=ivector(1,NSTACK);
338 Chapter 8. Sorting Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). i=j; j <<= 1; } else break; Found rra’s level. Terminate the sift-down. } ra[i]=rra; Put rra into its slot. } } CITED REFERENCES AND FURTHER READING: Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (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 concept of keys plays a prominent role in the management of data files. A data record in such a file may contain several items, or fields. For example, a record in a file of weather observations may have fields recording time, temperature, and wind velocity. When we sort the records, we must decide which of these fields we want to be brought into sorted order. The other fields in a record just come along for the ride, and will not, in general, end up in any particular order. The field on which the sort is performed is called the key field. For a data file with many records and many fields, the actual movement of N records into the sorted order of their keys Ki, i = 1,...,N, can be a daunting task. Instead, one can construct an index table I j , j = 1,...,N, such that the smallest Ki has i = I1, the second smallest has i = I2, and so on up to the largest Ki with i = IN . In other words, the array KIj j = 1, 2,...,N (8.4.1) is in sorted order when indexed by j. When an index table is available, one need not move records from their original order. Further, different index tables can be made from the same set of records, indexing them to different keys. The algorithm for constructing an index table is straightforward: Initialize the index array with the integers from 1 to N, then perform the Quicksort algorithm, moving the elements around as if one were sorting the keys. The integer that initially numbered the smallest key thus ends up in the number one position, and so on. #include "nrutil.h" #define SWAP(a,b) itemp=(a);(a)=(b);(b)=itemp; #define M 7 #define NSTACK 50 void indexx(unsigned long n, float arr[], unsigned long indx[]) Indexes an array arr[1..n], i.e., outputs the array indx[1..n] such that arr[indx[j]] is in ascending order for j = 1, 2,...,N. The input quantities n and arr are not changed. { unsigned long i,indxt,ir=n,itemp,j,k,l=1; int jstack=0,*istack; float a; istack=ivector(1,NSTACK);