342 Chapter 8.Sorting #define SWAP(a,b)temp=(a)(a)=(b);(b)=temp; float select(unsigned long k,unsigned long n,float arr[]) Returns the kth smallest value in the array arr[1..n].The input array will be rearranged to have this value in location arr[k],with all smaller elements moved to arr[1..k-1](in arbitrary order)and all larger elements in arr [k+1..n](also in arbitrary order). unsigned long i,ir,j,1,mid; float a,temp; 1=1: 1r=n; for(;;){ 1f(1r<=1+1)[ Active partition contains 1 or 2 elements. if (ir ==1+1&&arr[ir]arr[1]){ Case of 2 elements. SWAP(arr[1],arr[ir]) return arr[k]; else mid=(1+ir)>1; Choose median of left,center,and right el- SWAP(arr [mid],arr[1+1]) ements as partitioning element a.Also if (arr[l]arr[ir]){ rearrange so that arr[1]arr[1+1], SWAP(arr[1],arr[ir]) RECIPES I arr[ir]≥arr[1+1]. if (arr[1+1]arr[ir]){ SWAP(arr[1+1],arr[ir]) Press. if(arr[1]>arr[1+1])[ SWAP(arr[1],arr[1+1]) i=1+1; Initialize pointers for partitioning. j=1r; a=arr[1+1] Partitioning element. for(:;){ Beginning of innermost loop. IENTIFIC do i++;while (arr[i]a); Scan up to find element a. do j--;while (arr[j]a); Scan down to find element a. to dir if (i<i)break; Pointers crossed.Partitioning complete. SWAP(arr[i],arr[j]) End of innermost loop. arr[1+1]=arr[j]; Insert partitioning element 1992 arr[i]=a; (ISBN if(j>=k)1r=j-1; Keep active the partition that contains the 1f(j<=k)1=1; kth element. Numerica 10.621 22 uction Recipes 431086 (outside In-place,nondestructive,selection is conceptually simple,but it requires a lot of bookkeeping,and it is correspondingly slower.The general idea is to pick some Software. 首 number M of elements at random,to sort them,and then to make a pass through the array counting how many elements fall in each of the M+1 intervals defined by these elements.The kth largest will fall in one such interval-call it the "live" interval.One then does a second round,first picking M random elements in the live interval,and then determining which of the new,finer,M+1 intervals all presently live elements fall into.And so on,until the kth element is finally localized within a single array of size M,at which point direct selection is possible. How shall we pick M?The number of rounds,logM N log2 N/log2 M, will be smaller if M is larger;but the work to locate each element among M+1 subintervals will be larger,scaling as log2 M for bisection,say.Each round342 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). #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp; float select(unsigned long k, unsigned long n, float arr[]) Returns the kth smallest value in the array arr[1..n]. The input array will be rearranged to have this value in location arr[k], with all smaller elements moved to arr[1..k-1] (in arbitrary order) and all larger elements in arr[k+1..n] (also in arbitrary order). { unsigned long i,ir,j,l,mid; float a,temp; l=1; ir=n; for (;;) { if (ir <= l+1) { Active partition contains 1 or 2elements. if (ir == l+1 && arr[ir] < arr[l]) { Case of 2elements. SWAP(arr[l],arr[ir]) } return arr[k]; } else { mid=(l+ir) >> 1; Choose median of left, center, and right el￾ements as partitioning element a. Also rearrange so that arr[l] ≤ arr[l+1], arr[ir] ≥ arr[l+1]. SWAP(arr[mid],arr[l+1]) if (arr[l] > arr[ir]) { SWAP(arr[l],arr[ir]) } if (arr[l+1] > arr[ir]) { SWAP(arr[l+1],arr[ir]) } if (arr[l] > arr[l+1]) { SWAP(arr[l],arr[l+1]) } i=l+1; Initialize pointers for partitioning. j=ir; a=arr[l+1]; Partitioning element. for (;;) { Beginning of innermost loop. do i++; while (arr[i] < a); Scan up to find element > a. do j--; while (arr[j] > a); Scan down to find element < a. if (j < i) break; Pointers crossed. Partitioning complete. SWAP(arr[i],arr[j]) } End of innermost loop. arr[l+1]=arr[j]; Insert partitioning element. arr[j]=a; if (j >= k) ir=j-1; Keep active the partition that contains the if (j <= k) l=i; kth element. } } } In-place, nondestructive, selection is conceptually simple, but it requires a lot of bookkeeping, and it is correspondingly slower. The general idea is to pick some number M of elements at random, to sort them, and then to make a pass through the array counting how many elements fall in each of the M + 1 intervals defined by these elements. The kth largest will fall in one such interval — call it the “live” interval. One then does a second round, first picking M random elements in the live interval, and then determining which of the new, finer, M + 1 intervals all presently live elements fall into. And so on, until the kth element is finally localized within a single array of size M, at which point direct selection is possible. How shall we pick M? The number of rounds, logM N = log2 N/ log2 M, will be smaller if M is larger; but the work to locate each element among M + 1 subintervals will be larger, scaling as log2 M for bisection, say. Each round