8.5 Selecting the Mth Largest 341 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[1..n]as output from the routine indexx,returns an array irank[1..n],the corresponding table of ranks. f unsigned long j; for (j=1;j<=n;j++)irank[indx[j]]=j; Figure 8.4.1 summarizes the concepts discussed in this section 兰 83g 8.5 Selecting the Mth Largest NUMERICAL RECIPES I (Nort server 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 Programs 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 OF SCIENTIFIC 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 6 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 10621 bottom quartile elements.When N is odd,the median is the kth element,with Recipes Numerica k=(N+1)/2.When N is even,statistics books define the median as the arithmetic 431 mean of the elements k=N/2 and k=N/2+1 (that is,N/2 from the bottom E Recipes and N/2 from the top).If you accept such pedantry,you must perform two separate selections to find these elements.For N>100 we usually define k =N/2 to be the median element,pedants be damned. North The fastest general method for selection,allowing rearrangement,is partition- ing,exactly as was done in the Quicksort algorithm (88.2).Selecting a"random" partition element,one marches through the array,forcing smaller elements to the eft,larger elements to the right.As in Quicksort,it is important to optimize the inner loop,using "sentinels"(88.2)to minimize the number of comparisons.For sorting,one would then proceed to further partition both subsets.For selection, we can ignore one subset and attend only to the one that contains our desired kth element.Selection by partitioning thus does not need a stack of pending operations, and its operations count scales as N rather than as Nlog N (see [11).Comparison with sort in 88.2 should make the following routine obvious:8.5 Selecting the Mth Largest 341 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). 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[1..n] as output from the routine indexx, returns an array irank[1..n], the corresponding table of ranks. { unsigned long j; for (j=1;j<=n;j++) irank[indx[j]]=j; } Figure 8.4.1 summarizes the concepts discussed in this section. 8.5 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 perform two separate selections to find these elements. For N > 100 we usually define k = N/2 to be the median element, pedants be damned. The fastest general method for selection, allowing rearrangement, is partition￾ing, exactly as was done in the Quicksort algorithm (§8.2). Selecting a “random” partition element, one marches through the array, forcing smaller elements to the left, larger elements to the right. As in Quicksort, it is important to optimize the inner loop, using “sentinels” (§8.2) to minimize the number of comparisons. For sorting, one would then proceed to further partition both subsets. For selection, we can ignore one subset and attend only to the one that contains our desired kth element. Selection by partitioning thus does not need a stack of pending operations, and its operations count scales as N rather than as N log N (see [1]). Comparison with sort in §8.2 should make the following routine obvious: