Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C (523184), страница 80
Текст из файла (страница 80)
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 fordetailed 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 MethodStraight 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 theircards: Pick out the second card and put it in order with respect to the first; then pickout the third card and insert it into the sequence among the first two; and so on untilthe 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; arris replaced on output by its sorted rearrangement.{int i,j;float a;for (j=2;j<=n;j++) {a=arr[j];i=j-1;while (i > 0 && arr[i] > a) {arr[i+1]=arr[i];i--;}arr[i+1]=a;}Pick out each element in turn.Look for the place to insert it.Insert it.}What if you also want to rearrange an array brr at the same time as you sortarr? Simply move an element of brr whenever you move an element of arr:8.1 Straight Insertion and Shell’s Method331void piksr2(int n, float arr[], float brr[])Sorts an array arr[1..n] into ascending numerical order, by straight insertion, while makingthe corresponding rearrangement of the array brr[1..n].{int i,j;float a,b;for (j=2;j<=n;j++) {a=arr[j];b=brr[j];i=j-1;while (i > 0 && arr[i] > a) {arr[i+1]=arr[i];brr[i+1]=brr[i];i--;}arr[i+1]=a;brr[i+1]=b;}Pick out each element in turn.Look for the place to insert it.Insert it.}For the case of rearranging a larger number of arrays by sorting on one ofthem, see §8.4.Shell’s MethodThis 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,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). Nextsort 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.
Sowhat is the purpose of the previous partial sorts? The answer is that the previoussorts allow numbers efficiently to filter up or down to positions close to their finalresting places. Therefore, the straight insertion passes on the final sort rarely have togo past more than a “few” elements before finding the right place. (Think of sortinga hand of cards that are already almost in order.)The spacings between the numbers sorted on each pass through the data (8,4,2,1in the above example) are called the increments, and a Shell sort is sometimescalled a diminishing increment sort.
There has been a lot of research into how tochoose 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 muchbetter choice is the sequence(3k − 1)/2, . . .
, 40, 13, 4, 1(8.1.1)which can be generated by the recurrencei1 = 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 operationsrequired in all is of order N 3/2 for the worst possible ordering of the original data.332Chapter 8.SortingFor “randomly” ordered data, the operations count goes approximately as N 1.25, atleast for N < 60000.
For N > 50, however, Quicksort is generally faster. Theprogram follows:void shell(unsigned long n, float a[])Sorts an array a[1..n] into ascending numerical order by Shell’s method (diminishing incrementsort). n is input; a is replaced on output by its sorted rearrangement.{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 QuicksortQuicksort is, on most machines, on average, for large N , the fastest knownsorting algorithm. It is a “partition-exchange” sorting method: A “partitioningelement” a is selected from the array.
Then by pairwise exchanges of elements, theoriginal 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 repeatedon the left and right subarrays independently, and so on.The partitioning process is carried out by selecting some element, say theleftmost, as the partitioning element a. Scan a pointer up the array until you findan element > a, and then scan another pointer down from the end of the arrayuntil you find an element < a. These two elements are clearly out of place for thefinal partitioned array, so exchange them.
Continue this process until the pointerscross. This is the right place to insert a, and that round of partitioning is done. The8.2 Quicksort333question of the best strategy when an element is equal to the partitioning elementis subtle; we refer you to Sedgewick [1] for a discussion. (Answer: You shouldstop and do an exchange.)For speed of execution, we do not implement Quicksort using recursion. Thusthe algorithm requires an auxiliary array of storage, of length 2 log2 N , which it usesas a push-down stack for keeping track of the pending subarrays. When a subarrayhas gotten down to some size M , it becomes faster to sort it by straight insertion(§8.1), so we will do this.
The optimal setting of M is machine dependent, butM = 7 is not too far wrong. Some people advocate leaving the short subarraysunsorted until the end, and then doing one giant insertion sort at the end. Sinceeach element moves at most 7 places, this is just as efficient as doing the sortsimmediately, and saves on the overhead. However, on modern machines with pagedmemory, there is increased overhead when dealing with a large array all at once. Wehave not found any advantage in saving the insertion sorts till the end.As already mentioned, Quicksort’s average running time is fast, but its worstcase running time can be very slow: For the worst case it is, in fact, an N 2 method!And for the most straightforward implementation of Quicksort it turns out that theworst case is achieved for an input array that is already in order! This orderingof the input array might easily occur in practice.
One way to avoid this is to usea little random number generator to choose a random element as the partitioningelement. Another is to use instead the median of the first, middle, and last elementsof the current subarray.The great speed of Quicksort comes from the simplicity and efficiency of itsinner loop. Simply adding one unnecessary test (for example, a test that your pointerhas not moved off the end of the array) can almost double the running time! Oneavoids such unnecessary tests by placing “sentinels” at either end of the subarraybeing partitioned. The leftmost sentinel is ≤ a, the rightmost ≥ a. With the“median-of-three” selection of a partitioning element, we can use the two elementsthat were not the median to be the sentinels for that subarray.Our implementation closely follows [1]:#include "nrutil.h"#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;#define M 7#define NSTACK 50Here M is the size of subarrays sorted by straight insertion and NSTACK is the required auxiliarystorage.void sort(unsigned long n, float arr[])Sorts an array arr[1..n] into ascending numerical order using the Quicksort algorithm.
n isinput; arr is replaced on output by its sorted rearrangement.{unsigned long i,ir=n,j,k,l=1,*istack;int jstack=0;float a,temp;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];for (i=j-1;i>=l;i--) {if (arr[i] <= a) break;arr[i+1]=arr[i];334Chapter 8.Sorting}arr[i+1]=a;}if (jstack == 0) break;ir=istack[jstack--];Pop stack and begin a new round of partil=istack[jstack--];tioning.} else {k=(l+ir) >> 1;Choose median of left, center, and right elSWAP(arr[k],arr[l+1])ements as partitioning element a. Alsoif (arr[l] > arr[ir]) {rearrange so that a[l] ≤ a[l+1] ≤ a[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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
