c8-0 (779523)
Текст из файла
Sorting8.0 IntroductionThis chapter almost doesn’t belong in a book on numerical methods. However,some practical knowledge of techniques for sorting is an indispensable part of anygood programmer’s expertise. We would not want you to consider yourself expert innumerical techniques while remaining ignorant of so basic a subject.In conjunction with numerical work, sorting is frequently necessary when data(either experimental or numerically generated) are being handled.
One has tablesor lists of numbers, representing one or more independent (or “control”) variables,and one or more dependent (or “measured”) variables. One may wish to arrangethese data, in various circumstances, in order by one or another of these variables.Alternatively, one may simply wish to identify the “median” value, or the “upperquartile” value of one of the lists of values. This task, closely related to sorting,is called selection.Here, more specifically, are the tasks that this chapter will deal with:• Sort, i.e., rearrange, an array of numbers into numerical order.• Rearrange an array into numerical order while performing the corresponding rearrangement of one or more additional arrays, so that thecorrespondence between elements in all arrays is maintained.• Given an array, prepare an index table for it, i.e., a table of pointerstelling which number array element comes first in numerical order, whichsecond, and so on.• Given an array, prepare a rank table for it, i.e., a table telling what isthe numerical rank of the first array element, the second array element,and so on.• Select the M th largest element from an array.For the basic task of sorting N elements, the best algorithms require on theorder of several times N log2 N operations.
The algorithm inventor tries to reducethe constant in front of this estimate to as small a value as possible. Two of thebest algorithms are Quicksort (§8.2), invented by the inimitable C.A.R. Hoare, andHeapsort (§8.3), invented by J.W.J. Williams.For large N (say > 1000), Quicksort is faster, on most machines, by a factor of1.5 or 2; it requires a bit of extra memory, however, and is a moderately complicatedprogram. Heapsort is a true “sort in place,” and is somewhat more compact toprogram and therefore a bit easier to modify for special purposes. On balance, werecommend Quicksort because of its speed, but we implement both routines.329Sample 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).Chapter 8.330Chapter 8.SortingCITED 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: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).For small N one does better to use an algorithm whose operation count goesas a higher, i.e., poorer, power of N , if the constant in front is small enough.
ForN < 20, roughly, the method of straight insertion (§8.1) is concise and fast enough.We include it with some trepidation: It is an N 2 algorithm, whose potential formisuse (by using it for too large an N ) is great. The resultant waste of computertime is so awesome, that we were tempted not to include any N 2 routine at all. Wewill draw the line, however, at the inefficient N 2 algorithm, beloved of elementarycomputer science texts, called bubble sort. If you know what bubble sort is, wipe itfrom 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 toprogram than straight insertion, is competitive with the more complicated Quicksorton many machines. 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..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
