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 machine￾readable 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);