c8-2 (779525)
Текст из файла
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: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. 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).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);}8.2 Quicksort333#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];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).question 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]:334Chapter 8.Sorting}arr[i+1]=a;}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;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).}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.
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;}}8.2 Quicksort335Sample 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).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];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}}}CITED REFERENCES AND FURTHER READING:Sedgewick, R.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
