void rank(unsigned long n, unsigned long indx[], unsigned long irank[]) Given indx[1n] as output from the routine indexx, returns an array irank[1n], the corresponding table of ranks. { unsigned long j; for (j=1;j | 338 Chapter 8. Sorting if rra ra j ra i ra j i j j 1 else break ra i rra Demote rra. Found rra s level. Terminate the sift-down. Put rra into its slot. CITED REFERENCES AND FURTHER READING Knuth . 1973 Sorting and Searching vol. 3 of The Art ofComputer Programming Reading MA Addison-Wesley . 1 Sedgewick R. 1988 Algorithms 2nd ed. Reading MA Addison-Wesley Chapter 11. 2 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 orfields. 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 Ij j 1 . . . N such that the smallest Ki has i Ii the second smallest has i I2 and so on up to the largest Ki with i IN. In other words the array Kj j 1 2 . N 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 define SWAP a b itemp a a b b itemp define M 7 define NSTACK 50 Sample page from NUMERICAL RECIPES IN C THE ART OF .
