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;j0&&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 machinereadable 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 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:
8.1 Straight Insertion and Shell's Method 331 void piksr2(int n,float arr[],float brr[]) Sorts an array arr [1..n]into ascending numerical order,by straight insertion,while making the corresponding rearrangement of the array brr[1..n]. int i,j; float a,b; for (j=2;j0&&arr[i]a){ Look for the place to insert it. arr[i+1]=arr[i]; brr[i+1]=brr[i]; 1--； 83g d granted for 19881992 arr[i+1]=a; Insert it. brr[i+1]=b; 11800 from NUMERICAL RECIPES I For the case of rearranging a larger number of arrays by sorting on one of ⊙ them,see 88.4. Shell's Method 豆e3d Americ computer, This is actually a variant on straight insertion,but a very powerful variant indeed. The rough idea,e.g.,for the case of sorting 16 numbers n1...n16,is this:First sort, 9 by straight insertion,each of the 8 groups of 2 (n1,ng),(n2,n1o),...,(ns,n6). Next,sort each of the 4 groups of 4 (n1,n5,ng,n13),...,(n4,ns,n12,n16).Next SCIENTIFIC sort the 2 groups of 8 records,beginning with (n1,n3,n5,n7,ng,n11,n13,n15). Finally,sort the whole list of 16 numbers. Of course,only the last sort is necessary for putting the numbers into order.So what is the purpose of the previous partial sorts?The answer is that the previous sorts allow numbers efficiently to filter up or down to positions close to their final resting places.Therefore,the straight insertion passes on the final sort rarely have to go past more than a"few"elements before finding the right place.(Think of sorting Numerical 10-621 a hand of cards that are already almost in order. The spacings between the numbers sorted on each pass through the data(8,4,2,1 43106 in the above example)are called the increments,and a Shell sort is sometimes Recipes called a diminishing increment sort.There has been a lot of research into how to choose a good set of increments,but the optimum choice is not known.The set ...8,4,2,1 is in fact not a good choice,especially for N a power of 2.A much North better choice is the sequence (3-1)/2,..,40,13,4,1 (8.1.1) which can be generated by the recurrence i1=1, ik+1=3k+1,k=1,2,. (8.1.2) It can be shown (see 11])that for this sequence of increments the number of operations required in all is of order N3/2 for the worst possible ordering of the original data
8.1 Straight Insertion and Shell’s Method 331 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 machinereadable 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). void piksr2(int n, float arr[], float brr[]) Sorts an array arr[1..n] into ascending numerical order, by straight insertion, while making the corresponding rearrangement of the array brr[1..n]. { int i,j; float a,b; for (j=2;j 0 && arr[i] > a) { Look for the place to insert it. arr[i+1]=arr[i]; brr[i+1]=brr[i]; i--; } arr[i+1]=a; Insert it. brr[i+1]=b; } } For the case of rearranging a larger number of arrays by sorting on one of them, see §8.4. Shell’s Method This is actually a variant on straight insertion, but a very powerful variant indeed. The rough idea, e.g., for the case of sorting 16 numbers n 1 ...n16, is this: First sort, by straight insertion, each of the 8 groups of 2 (n1, n9), (n2, n10), ... , (n8, n16). Next, sort each of the 4 groups of 4 (n1, n5, n9, n13), ... , (n4, n8, n12, n16). Next sort the 2 groups of 8 records, beginning with (n1, n3, n5, n7, n9, n11, n13, n15). Finally, sort the whole list of 16 numbers. Of course, only the last sort is necessary for putting the numbers into order. So what is the purpose of the previous partial sorts? The answer is that the previous sorts allow numbers efficiently to filter up or down to positions close to their final resting places. Therefore, the straight insertion passes on the final sort rarely have to go past more than a “few” elements before finding the right place. (Think of sorting a hand of cards that are already almost in order.) The spacings between the numbers sorted on each pass through the data (8,4,2,1 in the above example) are called the increments, and a Shell sort is sometimes called a diminishing increment sort. There has been a lot of research into how to choose a good set of increments, but the optimum choice is not known. The set ..., 8, 4, 2, 1 is in fact not a good choice, especially for N a power of 2. A much better choice is the sequence (3k − 1)/2,..., 40, 13, 4, 1 (8.1.1) which can be generated by the recurrence i1 = 1, ik+1 = 3ik + 1, k = 1, 2,... (8.1.2) It can be shown (see [1]) that for this sequence of increments the number of operations required in all is of order N 3/2 for the worst possible ordering of the original data
332 Chapter 8.Sorting For"randomly"ordered data,the operations count goes approximately as N1.25,at least for N50,however,Quicksort is generally faster.The program follows: void shell(unsigned long n,float a[]) Sorts an array a]into ascending numerical order by Shell's method(diminishing increment sort).a is replaced on output by its sorted rearrangement.Normally,the argument n should be set to the size of array a,but if n is smaller than this,then only the first n elements of a are sorted.This feature is used in selip. unsigned long i,j,inc; float v; 1nc=1￥ Determine the starting increment. do inc *3; inc++; while (inc a.The process is then repeated on the left and right subarrays independently,and so on. The partitioning process is carried out by selecting some element,say the leftmost,as the partitioning element a.Scan a pointer up the array until you find an element a,and then scan another pointer down from the end of the array until you find an element<a.These two elements are clearly out of place for the final partitioned array,so exchange them.Continue this process until the pointers cross.This is the right place to insert a,and that round of partitioning is done.The
332 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 machinereadable 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 “randomly” ordered data, the operations count goes approximately as N 1.25, at least for N 50, however, Quicksort is generally faster. The program follows: void shell(unsigned long n, float a[]) Sorts an array a[] into ascending numerical order by Shell’s method (diminishing increment sort). a is replaced on output by its sorted rearrangement. Normally, the argument n should be set to the size of array a, but if n is smaller than this, then only the first n elements of a are sorted. This feature is used in selip. { unsigned long i,j,inc; float v; inc=1; Determine the starting increment. do { inc *= 3; inc++; } while (inc v) { Inner loop of straight insertion. a[j]=a[j-inc]; j -= inc; if (j 1); } CITED REFERENCES AND FURTHER READING: Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading, MA: Addison-Wesley), §5.2.1. [1] Sedgewick, R. 1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), Chapter 8. 8.2 Quicksort Quicksort is, on most machines, on average, for large N, the fastest known sorting algorithm. It is a “partition-exchange” sorting method: A “partitioning element” a is selected from the array. Then by pairwise exchanges of elements, the original array is partitioned into two subarrays. At the end of a round of partitioning, the element a is in its final place in the array. All elements in the left subarray are ≤ a, while all elements in the right subarray are ≥ a. The process is then repeated on the left and right subarrays independently, and so on. The partitioning process is carried out by selecting some element, say the leftmost, as the partitioning element a. Scan a pointer up the array until you find an element > a, and then scan another pointer down from the end of the array until you find an element < a. These two elements are clearly out of place for the final partitioned array, so exchange them. Continue this process until the pointers cross. This is the right place to insert a, and that round of partitioning is done. The