344 Chapter 8. Sorting FREEALL return ahi; sel [M+1]=sum/mm Augment selected set by mean value(fixes she11(M+1,se1); degeneracies),and sort it. sel[M+2]=ahi; for(j=1;j<=M+2;j++)ise1[j]=0; Zero the count array. for(i=1;1<=n;i+){ Make another pass through the array. if (arr[i]>=alo&&arr[i]<ahi){ For each in-range element.. j1=0; ju=M+2; while (ju-jl>1){ ...find its position among the select by jm=(ju+j1)/2; bisection... if (arr[i]>sel[jm])jl=jm; else ju=jm; 1se1[ju]+; ...and increment the counter. 2 j=1; Now we can narrow the bounds to just while (kk isel[j]){ one bin,that is,by a factor of order alo=sel[j]; kk-=1se1[j++]; ahi=sel[j]; Americ computer, Press. Approximate timings:selip is about 10 times slower than select.Indeed, 9 for N in the range of~10,selip is about 1.5 times slower than a full sort with sort,while select is about 6 times faster than sort.You should weigh time against memory and convenience carefully. SCIENTIFIC Of course neither of the above routines should be used for the trivial cases of finding the largest,or smallest,element in an array.Those cases,you code by hand as simple for loops.There are also good ways to code the case where k is modest in comparison to N,so that extra memory of order k is not burdensome.An example is to use the method of Heapsort(88.3)to make a single pass through an array of length N while saving the m largest elements.The advantage of the heap structure is that only log m,rather than m,comparisons are required every time a new element Numerica 10621 is added to the candidate list.This becomes a real savings when m >O(VN),but it never hurts otherwise and is easy to code.The following program gives the idea. uction 43106 Recipes void hpsel(unsigned long m,unsigned long n,float arr[],float heap[]) Returns in heap[1..m]the largest m elements of the array arr[1..n],with heap[1]guaran- (outside teed to be the the mth largest element.The array arr is not altered.For efficiency,this routine Software. should be used only when mn. North void sort(unsigned long n,float arr[]); void nrerror(char error_text []) unsigned long i,j,k; float swap; if (m n/2 II m 1)nrerror("probable misuse of hpsel"); for (i=1;i<=m;i++)heap[i]=arr[i]; sort(m,heap); Create initial heap by overkill!We assume mn. for(i=m+1;1<=n;1++)[ For each remaining element.. if (arr[i]heap[1]){ Put it on the heap? heap[1]=arr[i]; for(j=1;;){ Sift down.344 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). FREEALL return ahi; } sel[M+1]=sum/mm; Augment selected set by mean value (fixes shell(M+1,sel); degeneracies), and sort it. sel[M+2]=ahi; for (j=1;j<=M+2;j++) isel[j]=0; Zero the count array. for (i=1;i<=n;i++) { Make another pass through the array. if (arr[i] >= alo && arr[i] <= ahi) { For each in-range element.. jl=0; ju=M+2; while (ju-jl > 1) { ...find its position among the select by jm=(ju+jl)/2; bisection... if (arr[i] >= sel[jm]) jl=jm; else ju=jm; } isel[ju]++; ...and increment the counter. } } j=1; Now we can narrow the bounds to just one bin, that is, by a factor of order m. while (kk > isel[j]) { alo=sel[j]; kk -= isel[j++]; } ahi=sel[j]; } } Approximate timings: selip is about 10 times slower than select. Indeed, for N in the range of ∼ 105, selip is about 1.5 times slower than a full sort with sort, while select is about 6 times faster than sort. You should weigh time against memory and convenience carefully. Of course neither of the above routines should be used for the trivial cases of finding the largest, or smallest, element in an array. Those cases, you code by hand as simple for loops. There are also good ways to code the case where k is modest in comparison to N, so that extra memory of order k is not burdensome. An example is to use the method of Heapsort (§8.3) to make a single pass through an array of length N while saving the m largest elements. The advantage of the heap structure is that only log m, rather than m, comparisons are required every time a new element is added to the candidate list. This becomes a real savings when m>O( √N), but it never hurts otherwise and is easy to code. The following program gives the idea. void hpsel(unsigned long m, unsigned long n, float arr[], float heap[]) Returns in heap[1..m] the largest m elements of the array arr[1..n], with heap[1] guaran￾teed to be the the mth largest element. The array arr is not altered. For efficiency, this routine should be used only when m n. { void sort(unsigned long n, float arr[]); void nrerror(char error_text[]); unsigned long i,j,k; float swap; if (m > n/2 || m < 1) nrerror("probable misuse of hpsel"); for (i=1;i<=m;i++) heap[i]=arr[i]; sort(m,heap); Create initial heap by overkill! We assume m n. for (i=m+1;i<=n;i++) { For each remaining element... if (arr[i] > heap[1]) { Put it on the heap? heap[1]=arr[i]; for (j=1;;) { Sift down.