332 Chapter 8.Sorting For"randomly"ordered data,the operations count goes approximately as N1.25,at least for N<60000.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; 1nc=1￥ Determine the starting increment. do inc *3; inc++; while (inc <=n); e NUMERICAL do Loop over the partial sorts. inc /=3; for (i=inc+1;i<=n;i++){ Outer loop of straight insertion. to any v=a[i]; RECIPES I jsi; while (a[j-inc]v){ Inner loop of straight insertion. a[i]=a[j-inc]; j-=inc; (North America 州bMe se to make one paper University Press. THE if (j <inc)break; 2 ART a[i]-v; while (inc 1); Programs IENTIFIC CITED REFERENCES AND FURTHER READING: Knuth.D.E.1973.Sorting and Searching,vol.3 of The Art of Computer Programming(Reading. MA:Addison-Wesley),85.2.1.[1] COMPUTING Sedgewick,R.1988,Algorithms,2nd ed.(Reading,MA:Addison-Wesley),Chapter 8. 192 Fuunrggoirioh (ISBN 10.621 8.2 Quicksort Numerica Recipes 43108 Quicksort is,on most machines,on average,for large N,the fastest known (outside 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 首 Software. 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.The332 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 “randomly” ordered data, the operations count goes approximately as N 1.25, at least for N < 60000. 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 <= n); do { Loop over the partial sorts. inc /= 3; for (i=inc+1;i<=n;i++) { Outer loop of straight insertion. v=a[i]; j=i; while (a[j-inc] > v) { Inner loop of straight insertion. a[j]=a[j-inc]; j -= inc; if (j <= inc) break; } a[j]=v; } } while (inc > 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