c8-4 (779527)
Текст из файла
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, .
. . , N . The input quantities n and arr are not changed.{unsigned long i,indxt,ir=n,itemp,j,k,l=1;int jstack=0,*istack;float a;Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).}3398.4 Indexing and Rankingoriginalarrayindextableranktablesortedarray54314118423231556(b)15536144615(a)245831366347227532341326(c)(d)Figure 8.4.1. (a) An unsorted array of six numbers. (b) Index table, whose entries are pointers tothe elements of (a) in ascending order.
(c) Rank table, whose entries are the ranks of the correspondingelements of (a). (d) Sorted array of the elements in (a).istack=ivector(1,NSTACK);for (j=1;j<=n;j++) indx[j]=j;for (;;) {if (ir-l < M) {for (j=l+1;j<=ir;j++) {indxt=indx[j];a=arr[indxt];for (i=j-1;i>=l;i--) {if (arr[indx[i]] <= a) break;indx[i+1]=indx[i];}indx[i+1]=indxt;}if (jstack == 0) break;ir=istack[jstack--];l=istack[jstack--];} else {k=(l+ir) >> 1;SWAP(indx[k],indx[l+1]);if (arr[indx[l]] > arr[indx[ir]]) {SWAP(indx[l],indx[ir])}if (arr[indx[l+1]] > arr[indx[ir]]) {SWAP(indx[l+1],indx[ir])}if (arr[indx[l]] > arr[indx[l+1]]) {SWAP(indx[l],indx[l+1])}i=l+1;j=ir;indxt=indx[l+1];Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).21340Chapter 8.Sorting}}free_ivector(istack,1,NSTACK);}If you want to sort an array while making the corresponding rearrangement ofseveral or many other arrays, you should first make an index table, then use it torearrange each array in turn. This requires two arrays of working space: one tohold the index, and another into which an array is temporarily moved, and fromwhich it is redeposited back on itself in the rearranged order.
For 3 arrays, theprocedure looks like this:#include "nrutil.h"void sort3(unsigned long n, float ra[], float rb[], float rc[])Sorts an array ra[1..n] into ascending numerical order while making the corresponding rearrangements of the arrays rb[1..n] and rc[1..n]. An index table is constructed via theroutine indexx.{void indexx(unsigned long n, float arr[], unsigned long indx[]);unsigned long j,*iwksp;float *wksp;iwksp=lvector(1,n);wksp=vector(1,n);indexx(n,ra,iwksp);for (j=1;j<=n;j++) wksp[j]=ra[j];for (j=1;j<=n;j++) ra[j]=wksp[iwksp[j]];for (j=1;j<=n;j++) wksp[j]=rb[j];for (j=1;j<=n;j++) rb[j]=wksp[iwksp[j]];for (j=1;j<=n;j++) wksp[j]=rc[j];for (j=1;j<=n;j++) rc[j]=wksp[iwksp[j]];free_vector(wksp,1,n);free_lvector(iwksp,1,n);Make the index table.Save the array ra.Copy it back in rearranged order.Ditto rb.Ditto rc.}The generalization to any other number of arrays is obviously straightforward.A rank table is different from an index table.
A rank table’s jth entry gives theSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).a=arr[indxt];for (;;) {do i++; while (arr[indx[i]] < a);do j--; while (arr[indx[j]] > a);if (j < i) break;SWAP(indx[i],indx[j])}indx[l+1]=indx[j];indx[j]=indxt;jstack += 2;if (jstack > NSTACK) nrerror("NSTACK too small in indexx.");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;}8.5 Selecting the Mth Largest341rank of the jth element of the original array of keys, ranging from 1 (if that elementwas the smallest) to N (if that element was the largest).
One can easily constructa rank table from an index table, however:for (j=1;j<=n;j++) irank[indx[j]]=j;}Figure 8.4.1 summarizes the concepts discussed in this section.8.5 Selecting the Mth LargestSelection is sorting’s austere sister. (Say that five times quickly!) Where sortingdemands the rearrangement of an entire data array, selection politely asks for a singlereturned value: What is the kth smallest (or, equivalently, the m = N +1−kth largest)element out of N elements? The fastest methods for selection do, unfortunately,rearrange the array for their own computational purposes, typically putting all smallerelements to the left of the kth, all larger elements to the right, and scrambling theorder within each subset. This side effect is at best innocuous, at worst downrightinconvenient. When the array is very long, so that making a scratch copy of it is taxingon memory, or when the computational burden of the selection is a negligible partof a larger calculation, one turns to selection algorithms without side effects, whichleave the original array undisturbed.
Such in place selection is slower than the fasterselection methods by a factor of about 10. We give routines of both types, below.The most common use of selection is in the statistical characterization of a setof data. One often wants to know the median element in an array, or the top andbottom quartile elements. When N is odd, the median is the kth element, withk = (N + 1)/2.
When N is even, statistics books define the median as the arithmeticmean of the elements k = N/2 and k = N/2 + 1 (that is, N/2 from the bottomand N/2 from the top). If you accept such pedantry, you must perform two separateselections to find these elements. For N > 100 we usually define k = N/2 to bethe median element, pedants be damned.The fastest general method for selection, allowing rearrangement, is partitioning, exactly as was done in the Quicksort algorithm (§8.2). Selecting a “random”partition element, one marches through the array, forcing smaller elements to theleft, larger elements to the right. As in Quicksort, it is important to optimize theinner loop, using “sentinels” (§8.2) to minimize the number of comparisons. Forsorting, one would then proceed to further partition both subsets.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
