8.2 Quicksort 333 question of the best strategy when an element is equal to the partitioning element is subtle;we refer you to Sedgewick [1]for a discussion.(Answer:You should stop and do an exchange. For speed of execution,we do not implement Quicksort using recursion.Thus the algorithm requires an auxiliary array of storage,of length 2 log2 N,which it uses as a push-down stack for keeping track of the pending subarrays.When a subarray has gotten down to some size M,it becomes faster to sort it by straight insertion (88.1),so we will do this.The optimal setting of M is machine dependent,but M =7 is not too far wrong.Some people advocate leaving the short subarrays unsorted until the end,and then doing one giant insertion sort at the end.Since 81 each element moves at most 7 places,this is just as efficient as doing the sorts immediately,and saves on the overhead.However,on modern machines with paged memory,there is increased overhead when dealing with a large array all at once.We have not found any advantage in saving the insertion sorts till the end. As already mentioned,Quicksort's average running time is fast,but its worst case running time can be very slow:For the worst case it is,in fact,an N2 method! And for the most straightforward implementation of Quicksort it turns out that the worst case is achieved for an input array that is already in order!This ordering of the input array might easily occur in practice.One way to avoid this is to use a little random number generator to choose a random element as the partitioning element.Another is to use instead the median of the first.middle.and last elements as Press. of the current subarray. The great speed of Quicksort comes from the simplicity and efficiency of its 9 inner loop.Simply adding one unnecessary test(for example,a test that your pointer has not moved off the end of the array)can almost double the running time!One avoids such unnecessary tests by placing"sentinels"at either end of the subarray being partitioned.The leftmost sentinel is a,the rightmost a.With the 6 "median-of-three"selection of a partitioning element,we can use the two elements that were not the median to be the sentinels for that subarray. Our implementation closely follows [1]: COMPUTING (ISBN 188812920 #include "nrutil.h" #define SWAP(a,b)temp=(a)(a)=(b);(b)=temp; 10.621 #define M 7 #define NSTACK 50 uurggoglrion Here M is the size of subarrays sorted by straight insertion and NSTACK is the required auxiliary Numerical Recipes 43106 storage. void sort(nsigned long n,f1 oat arr门） (outside Sorts an array arr [1..n]into ascending numerical order using the Quicksort algorithm.n is Software. input;arr is replaced on output by its sorted rearrangement. North unsigned long i,ir=n,j,k,1=1,*istack; int jstack=0; float a,tempi istack=lvector(1,NSTACK); for（;;){ Insertion sort when subarray small enough. if(1r-1<)[ for(j=1+1;j<=ir;j+)[ a=arr[j]; for(i=j-1;1>=1;1--)[ if (arr[i]<a)break; arr[i+1]sarr[i];8.2 Quicksort 333 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). question of the best strategy when an element is equal to the partitioning element is subtle; we refer you to Sedgewick [1] for a discussion. (Answer: You should stop and do an exchange.) For speed of execution, we do not implement Quicksort using recursion. Thus the algorithm requires an auxiliary array of storage, of length 2 log 2 N, which it uses as a push-down stack for keeping track of the pending subarrays. When a subarray has 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, but M = 7 is not too far wrong. Some people advocate leaving the short subarrays unsorted until the end, and then doing one giant insertion sort at the end. Since each element moves at most 7 places, this is just as efficient as doing the sorts immediately, and saves on the overhead. However, on modern machines with paged memory, there is increased overhead when dealing with a large array all at once. We have not found any advantage in saving the insertion sorts till the end. As already mentioned, Quicksort’s average running time is fast, but its worst case 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 the worst case is achieved for an input array that is already in order! This ordering of the input array might easily occur in practice. One way to avoid this is to use a little random number generator to choose a random element as the partitioning element. Another is to use instead the median of the first, middle, and last elements of the current subarray. The great speed of Quicksort comes from the simplicity and efficiency of its inner loop. Simply adding one unnecessary test (for example, a test that your pointer has not moved off the end of the array) can almost double the running time! One avoids such unnecessary tests by placing “sentinels” at either end of the subarray being partitioned. The leftmost sentinel is ≤ a, the rightmost ≥ a. With the “median-of-three” selection of a partitioning element, we can use the two elements that 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 50 Here M is the size of subarrays sorted by straight insertion and NSTACK is the required auxiliary storage. void sort(unsigned long n, float arr[]) Sorts an array arr[1..n] into ascending numerical order using the Quicksort algorithm. n is input; 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];