rank of the jth element of the original array of keys, ranging from 1 (if that element was the smallest) to N (if that element was the largest). One can easily construct a rank table from an index table | Selecting the Mth Largest 341 rank of the jth element of the original array of keys ranging from 1 if that element was the smallest to N if that element was the largest . One can easily construct a rank table from an index table however void rank unsigned long n unsigned long indx unsigned long irank Given indx as output from the routine indexx returns an array irank the corresponding table of ranks. unsigned long j for j 1 j n j irank indx j j Figure summarizes the concepts discussed in this section. Selecting the Mth Largest Selection is sorting s austere sister. Say that five times quickly Where sorting demands the rearrangement of an entire data array selection politely asks for a single returned value What is the kth smallest or equivalently the m N 1-kth largest element out of N elements The fastest methods for selection do unfortunately rearrange the array for their own computational purposes typically putting all smaller elements to the left of the kth all larger elements to the right and scrambling the order within each subset. This side effect is at best innocuous at worst downright inconvenient. When the array is very long so that making a scratch copy of it is taxing on memory or when the computational burden of the selection is a negligible part of a larger calculation one turns to selection algorithms without side effects which leave the original array undisturbed. Such in place selection is slower than the faster selection methods by a factor of about 10. We give routines of both types below. The most common use of selection is in the statistical characterization of a set of data. One often wants to know the median element in an array or the top and bottom quartile elements. When N is odd the median is the kth element with k N 1 2. When N is even statistics books define the median as the arithmetic mean of the elements k N 2 and k N 2 1 that is N 2 from the bottom and N 2 from the top . If you accept such pedantry you must .
