8.2 Quicksort 335 istack=lvector(1,NSTACK); for(;;){ Insertion sort when subarray small enough. if(1r-1<M)[ for(j=1+1;j<=1r:j+)( asarr[i]; b=brr[j]; for(1=j-1;1>=1;1-)[ if (arr[i]<a)break; arr[i+1]=arr[i]; brr[i+1]=brr[i]; arr[i+1]=a; read able files Permission is brr[i+1]=b; 2 if (!jstack){ 83g free_lvector(istack,1,NSTACK); return; 11-600 (including this one) granted fori ir=istack[jstack]: Pop stack and begin a new round of parti- l=istack[istack-1]; tioning. jstack -2; else from NUMERICAL RECIPES IN k=(1+1r)>>1: Choose median of left,center and right el- SWAP(arr [k]arr [1+1]) ements as partitioning element a.Also SWAP(brr [k],brr[1+1]) rearrange so that a[]≤a[1+1]≤a[ir]. (North if (arr[l]arr[ir]){ America to any server computer, SWAP(arr[1],arr[ir]) tusers to make one paper 1988-1992 by Cambridge University Press.Programs THE SWAP(brr[1],brr[ir]) only). ART if (arr[1+1]arr[ir]){ SWAP(arr[1+1],arr[ir]) SWAP(brr[1+1],brr[ir]) copy for their 2 if(arr[1]>arr[1+1])[ strictly prohibited. SWAP(arr[1],arr[1+1]) Copyright (C) SWAP(brr[1],brr[1+1]) 1=1+1; Initialize pointers for partitioning. j=ir; a=arr[1+1]: Partitioning element. b=brr[1+1]; OF SCIENTIFIC COMPUTING(ISBN 0-521 for (;;) Beginning of innermost loop. doi++;while (arr[i]a); Scan up to find element a. v@cambri do j--;while (arr[j]a); Scan down to find element a. if (i<i)break; Pointers crossed.Partitioning complete. SWAP(arr[i],arr[j]) Exchange elements of both arrays. ea/Recipes≤oO30aS 1988-1992 by Numerical Recipes SWAP(brr[i],brr[]) -431085 End of innermost loop. arr[1+1]=arr[j]; Insert partitioning element in both arrays. (outside arr[j]=a; brr[1+1]=brr[j]; North Software. brr[j]=b; jstack +2; ying of Push pointers to larger subarray on stack,process smaller subarray immediately if (istack NSTACK)nrerror("NSTACK too small in sort2."); f(ir-i+1>=j-1)[ istack[jstack]=ir; istack[istack-1]=i; 1r=j-1; else istack[jstack]=j-1; istack[istack-1]=l; 1=1;8.2 Quicksort 335 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). istack=lvector(1,NSTACK); for (;;) { Insertion sort when subarray small enough. if (ir-l < M) { for (j=l+1;j<=ir;j++) { a=arr[j]; b=brr[j]; for (i=j-1;i>=l;i--) { if (arr[i] <= a) break; arr[i+1]=arr[i]; brr[i+1]=brr[i]; } arr[i+1]=a; brr[i+1]=b; } if (!jstack) { free_lvector(istack,1,NSTACK); return; } ir=istack[jstack]; Pop stack and begin a new round of parti￾l=istack[jstack-1]; tioning. jstack -= 2; } else { k=(l+ir) >> 1; Choose median of left, center and right el￾ements as partitioning element a. Also rearrange so that a[l] ≤ a[l+1] ≤ a[ir]. SWAP(arr[k],arr[l+1]) SWAP(brr[k],brr[l+1]) if (arr[l] > arr[ir]) { SWAP(arr[l],arr[ir]) SWAP(brr[l],brr[ir]) } if (arr[l+1] > arr[ir]) { SWAP(arr[l+1],arr[ir]) SWAP(brr[l+1],brr[ir]) } if (arr[l] > arr[l+1]) { SWAP(arr[l],arr[l+1]) SWAP(brr[l],brr[l+1]) } i=l+1; Initialize pointers for partitioning. j=ir; a=arr[l+1]; Partitioning element. b=brr[l+1]; 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]) Exchange elements of both arrays. SWAP(brr[i],brr[j]) } End of innermost loop. arr[l+1]=arr[j]; Insert partitioning element in both arrays. arr[j]=a; brr[l+1]=brr[j]; brr[j]=b; jstack += 2; Push pointers to larger subarray on stack, process smaller subarray immediately. if (jstack > NSTACK) nrerror("NSTACK too small in sort2."); if (ir-i+1 >= j-l) { istack[jstack]=ir; istack[jstack-1]=i; ir=j-1; } else { istack[jstack]=j-1; istack[jstack-1]=l; l=i; }