330 Chapter 8.Sorting For small N one does better to use an algorithm whose operation count goes as a higher,i.e.,poorer,power of N,if the constant in front is small enough.For N 20,roughly,the method of straight insertion (88.1)is concise and fast enough. We include it with some trepidation:It is an N2 algorithm,whose potential for misuse(by using it for too large an N)is great.The resultant waste of computer time is so awesome,that we were tempted not to include any N2 routine at all.We will draw the line,however,at the inefficient N2 algorithm,beloved of elementary computer science texts,called bubble sort.If you know what bubble sort is,wipe it from your mind:if you don't know,make a point of never finding out! 三 For N 50,roughly,Shell's method ($8.1),only slightly more complicated to program than straight insertion,is competitive with the more complicated Quicksort on many machines.This method goes as N3/2 in the worst case,but is usually faster. See references [1.2]for further information on the subject of sorting,and for detailed references to the literature. 的 CITED REFERENCES AND FURTHER READING: Knuth,D.E.1973.Sorting and Searching.vol.3 of The Art of Computer Programming(Reading. MA:Addison-Wesley).[1] Sedgewick,R.1988,Algorithms,2nd ed.(Reading,MA:Addison-Wesley),Chapters 8-13.[2] 、当%a 令 Press. 9访 8.1 Straight Insertion and Shell's Method OF SCIENTIFIC Straight insertion is an N2 routine,and should be used only for small N. say 20. The technique is exactly the one used by experienced card players to sort their cards:Pick out the second card and put it in order with respect to the first:then pick out the third card and insert it into the sequence among the first two;and so on until 、兰学% COMPUTING (ISBN 188810920 the last card has been picked out and inserted. 10621 void piksrt(int n,float arr[]) Sorts an array arr[1..n]into ascending numerical order,by straight insertion.n is input;arr is replaced on output by its sorted rearrangement. uurggoglrion 43106 f Numerical Recipes int i,ji float a; (outside for (j=2;j<=n;j++) Pick out each element in turn. Software. a=arr[j]; 1=j-1; ying of while (i >0&&arr[i]a){ Look for the place to insert it. arr[i+i]sarr[i]; 1--； arr[i+1]=a; Insert it. What if you also want to rearrange an array brr at the same time as you sort arr?Simply move an element of brr whenever you move an element of arr:330 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). For small N one does better to use an algorithm whose operation count goes as a higher, i.e., poorer, power of N, if the constant in front is small enough. For N < 20, roughly, the method of straight insertion (§8.1) is concise and fast enough. We include it with some trepidation: It is an N 2 algorithm, whose potential for misuse (by using it for too large an N) is great. The resultant waste of computer time is so awesome, that we were tempted not to include any N 2 routine at all. We will draw the line, however, at the inefficient N 2 algorithm, beloved of elementary computer science texts, called bubble sort. If you know what bubble sort is, wipe it from your mind; if you don’t know, make a point of never finding out! For N < 50, roughly, Shell’s method (§8.1), only slightly more complicated to program than straight insertion, is competitive with the more complicated Quicksort on many machines. This method goes as N 3/2 in the worst case, but is usually faster. See references [1,2] for further information on the subject of sorting, and for detailed references to the literature. CITED REFERENCES AND FURTHER READING: Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading, MA: Addison-Wesley). [1] Sedgewick, R. 1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), Chapters 8–13. [2] 8.1 Straight Insertion and Shell’s Method Straight insertion is an N 2 routine, and should be used only for small N, say < 20. The technique is exactly the one used by experienced card players to sort their cards: Pick out the second card and put it in order with respect to the first; then pick out the third card and insert it into the sequence among the first two; and so on until the last card has been picked out and inserted. void piksrt(int n, float arr[]) Sorts an array arr[1..n] into ascending numerical order, by straight insertion. n is input; arr is replaced on output by its sorted rearrangement. { int i,j; float a; for (j=2;j<=n;j++) { Pick out each element in turn. a=arr[j]; i=j-1; while (i > 0 && arr[i] > a) { Look for the place to insert it. arr[i+1]=arr[i]; i--; } arr[i+1]=a; Insert it. } } What if you also want to rearrange an array brr at the same time as you sort arr? Simply move an element of brr whenever you move an element of arr: