Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C (523184), страница 81
Текст из файла (страница 81)
Partitioning complete.SWAP(arr[i],arr[j]);Exchange elements.}End of innermost loop.arr[l+1]=arr[j];Insert partitioning element.arr[j]=a;jstack += 2;Push pointers to larger subarray on stack, process smaller subarray immediately.if (jstack > NSTACK) nrerror("NSTACK too small in sort.");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;}}}free_lvector(istack,1,NSTACK);}As usual you can move any other arrays around at the same time as you sortarr. At the risk of being repetitious:#include "nrutil.h"#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;#define M 7#define NSTACK 50void sort2(unsigned long n, float arr[], float brr[])Sorts an array arr[1..n] into ascending order using Quicksort, while making the correspondingrearrangement of the array brr[1..n].{unsigned long i,ir=n,j,k,l=1,*istack;int jstack=0;float a,b,temp;8.2 Quicksort335istack=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 partil=istack[jstack-1];tioning.jstack -= 2;} else {k=(l+ir) >> 1;Choose median of left, center and right elSWAP(arr[k],arr[l+1])ements as partitioning element a.
AlsoSWAP(brr[k],brr[l+1])rearrange so that a[l] ≤ a[l+1] ≤ a[ir].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;}336Chapter 8.Sorting}}}You could, in principle, rearrange any number of additional arrays along withbrr, but this becomes wasteful as the number of such arrays becomes large. Thepreferred technique is to make use of an index table, as described in §8.4.CITED REFERENCES AND FURTHER READING:Sedgewick, R.
1978, Communications of the ACM, vol. 21, pp. 847–857. [1]8.3 HeapsortWhile usually not quite as fast as Quicksort, Heapsort is one of our favoritesorting routines. It is a true “in-place” sort, requiring no auxiliary storage. It is anN log2 N process, not only on average, but also for the worst-case order of input data.In fact, its worst case is only 20 percent or so worse than its average running time.It is beyond our scope to give a complete exposition on the theory of Heapsort.We will mention the general principles, then let you refer to the references [1,2] , oranalyze the program yourself, if you want to understand the details.A set of N numbers ai , i = 1, .
. . , N , is said to form a “heap” if it satisfiesthe relationaj/2 ≥ ajfor 1 ≤ j/2 < j ≤ N(8.3.1)Here the division in j/2 means “integer divide,” i.e., is an exact integer or elseis rounded down to the closest integer. Definition (8.3.1) will make sense if youthink of the numbers ai as being arranged in a binary tree, with the top, “boss,”node being a1 , the two “underling” nodes being a2 and a3 , their four underlingnodes being a4 through a7 , etc.
(See Figure 8.3.1.) In this form, a heap hasevery “supervisor” greater than or equal to its two “supervisees,” down throughthe levels of the hierarchy.If you have managed to rearrange your array into an order that forms a heap,then sorting it is very easy: You pull off the “top of the heap,” which will be thelargest element yet unsorted. Then you “promote” to the top of the heap its largestunderling. Then you promote its largest underling, and so on. The process is likewhat happens (or is supposed to happen) in a large corporation when the chairmanof the board retires. You then repeat the whole process by retiring the new chairmanof the board.
Evidently the whole thing is an N log2 N process, since each retiringchairman leads to log2 N promotions of underlings.Well, how do you arrange the array into a heap in the first place? The answeris again a “sift-up” process like corporate promotion.
Imagine that the corporationstarts out with N/2 employees on the production line, but with no supervisors. Nowa supervisor is hired to supervise two workers. If he is less capable than one ofhis workers, that one is promoted in his place, and he joins the production line.3378.3 Heapsorta1a2a3a4a8a5a9a10a6a11a7a12Figure 8.3.1.
Ordering implied by a “heap,” here of 12 elements. Elements connected by an upwardpath are sorted with respect to one another, but there is not necessarily any ordering among elementsrelated only “laterally.”After supervisors are hired, then supervisors of supervisors are hired, and so on upthe corporate ladder. Each employee is brought in at the top of the tree, but thenimmediately sifted down, with more capable workers promoted until their propercorporate level has been reached.In the Heapsort implementation, the same “sift-up” code can be used for theinitial creation of the heap and for the subsequent retirement-and-promotion phase.One execution of the Heapsort function represents the entire life-cycle of a giantcorporation: N/2 workers are hired; N/2 potential supervisors are hired; there is asifting up in the ranks, a sort of super Peter Principle: in due course, each of theoriginal employees gets promoted to chairman of the board.void hpsort(unsigned long n, float ra[])Sorts an array ra[1..n] into ascending numerical order using the Heapsort algorithm.
n isinput; ra is replaced on output by its sorted rearrangement.{unsigned long i,ir,j,l;float rra;if (n < 2) return;l=(n >> 1)+1;ir=n;The index l will be decremented from its initial value down to 1 during the “hiring” (heapcreation) phase. Once it reaches 1, the index ir will be decremented from its initial valuedown to 1 during the “retirement-and-promotion” (heap selection) phase.for (;;) {if (l > 1) {Still in hiring phase.rra=ra[--l];} else {In retirement-and-promotion phase.rra=ra[ir];Clear a space at end of array.ra[ir]=ra[1];Retire the top of the heap into it.if (--ir == 1) {Done with the last promotion.ra[1]=rra;The least competent worker of all!break;}}i=l;Whether in the hiring phase or promotion phase, wej=l+l;here set up to sift down element rra to its properwhile (j <= ir) {level.if (j < ir && ra[j] < ra[j+1]) j++; Compare to the better underling.338Chapter 8.if (rra < ra[j]) {ra[i]=ra[j];i=j;j <<= 1;} else break;}ra[i]=rra;SortingDemote rra.Found rra’s level.
Terminate the sift-down.Put rra into its slot.}}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.3. [1]Sedgewick, R. 1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), Chapter 11. [2]8.4 Indexing and RankingThe concept of keys plays a prominent role in the management of data files.
Adata record in such a file may contain several items, or fields. For example, a recordin a file of weather observations may have fields recording time, temperature, andwind velocity. When we sort the records, we must decide which of these fields wewant to be brought into sorted order. The other fields in a record just come alongfor the ride, and will not, in general, end up in any particular order.
The field onwhich the sort is performed is called the key field.For a data file with many records and many fields, the actual movement of Nrecords into the sorted order of their keys Ki , i = 1, . . . , N , can be a daunting task.Instead, one can construct an index table Ij , j = 1, . . . , N , such that the smallestKi has i = I1 , the second smallest has i = I2 , and so on up to the largest Ki withi = IN . In other words, the arrayKIjj = 1, 2, . .
. , N(8.4.1)is in sorted order when indexed by j. When an index table is available, one need notmove records from their original order. Further, different index tables can be madefrom the same set of records, indexing them to different keys.The algorithm for constructing an index table is straightforward: Initialize theindex array with the integers from 1 to N , then perform the Quicksort algorithm,moving the elements around as if one were sorting the keys. The integer that initiallynumbered the smallest key thus ends up in the number one position, and so on.#include "nrutil.h"#define SWAP(a,b) itemp=(a);(a)=(b);(b)=itemp;#define M 7#define NSTACK 50void indexx(unsigned long n, float arr[], unsigned long indx[])Indexes an array arr[1..n], i.e., outputs the array indx[1..n] such that arr[indx[j]] isin ascending order for j = 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
