Lecture 9:Linear SortingSteven SkienaDepartment of Computer ScienceState University of New YorkStony Brook, NY 11794–4400http://www.cs.sunysb.edu/∼skienaProblem of the DayThe nuts and bolts problem is defined as follows. Youare given a collection of n bolts of different widths, and ncorresponding nuts. You can test whether a given nut and bolttogether, from which you learn whether the nut is too large,too small, or an exact match for the bolt. The differences insize between pairs of nuts or bolts can be too small to see byeye, so you cannot rely on comparing the sizes of two nuts ortwo bolts directly. You are to match each bolt to each nut.1. Give an O(n2) algorithm to solve the nuts and boltsproblem.2. Suppose that instead of matching all of the nuts and bolts,you wish to find the smallest bolt and its correspondingnut. Show that this can be done in only 2n − 2comparisons.3. Match the nuts and bolts in expected O(n log n) time.SolutionQuicksort PseudocodeSort(A)Quicksort(A,1,n)Quicksort(A, low, high)if (low < high)pivot-location = Partition(A,low,high)Quicksort(A,low, pivot-location - 1)Quicksort(A, pivot-location+1, high)Partition ImplementationPartition(A,low,high)pivot = A[low]leftwall = lowfor i = low+1 to highif (A[i] < pivot) thenleftwall = leftwall+1swap(A[i],A[leftwall])swap(A[low],A[leftwall])Quicksort AnimationQ U I C K S O R TQ I C K S O R T UQ I C K O R S T UI C K O Q R S T UI C K O Q R S T UI C K O Q R S T UBest Case for QuicksortSince each element ultimately ends up in the correct position,the algorithm correctly sorts. But how long does it take?The best case for divide-and-conquer algorithms comes whenwe split the input as evenly as possible. Thus in the best case,each subproblem is of size n/2.The partition step on each subproblem is linear in its size.Thus the total effort in partitioning the 2kproblems of sizen/2kis O(n).Best Case Recursion TreeThe total partitioning on each level is O(n), and it takelg n levels of perfect partitions to get to single elementsubproblems. When we are down to single elements, theproblems are sorted. Thus the total time in the best case isO(n lg n).Worst Case for QuicksortSuppose instead our pivot element splits the array asunequally as possible. Thus instead of n/2 elements in thesmaller half, we get zero, meaning that the pivot element isthe biggest or smallest element in the array.Now we have n−1 levels, instead of lg n, for a worst case timeof Θ(n2), since the first n/2 levels each have ≥ n/2 elementsto partition.To justify its name, Quicksort had better be good in theaverage case. Showing this requires some intricate analysis.The divide and conquer principle applies to real life. If youbreak a job into pieces, make the pieces of equal size!Intuition: The Average Case for QuicksortSuppose we pick the pivot element at random in an array of nkeys.1 n/4 3n/4 nn/2Half the time, the pivot element will be from the center halfof the sorted array.Whenever the pivot element is from positions n/4 to 3n/4, thelarger remaining subarray contains at most 3n/4 elements.How Many Good PartitionsIf we assume that the pivot element is always in this range,what is the maximum number of partitions we need to getfrom n elements down to 1 element?(3/4)l· n = 1 −→ n = (4/3)llg n = l · lg(4/3)Therefore l = lg(4/3) · lg(n) < 2 lg n good partitions suffice.How Many Bad Partitions?How often when we pick an arbitrary element as pivot will itgenerate a decent partition?Since any number ranked between n/4 and 3n/4 would makea decent pivot, we get one half the time on average.If we need 2 lg n levels of decent partitions to finish the job,and half of random partitions are decent, then on average therecursion tree to quicksort the array has ≈ 4 lg n levels.Since O(n) work is done partitioning on each level, theaverage time is O(n lg n).Average-Case Analysis of Quicksort (*)To do a precise average-case analysis of quicksort, weformulate a recurrence given the exact expected time T (n):T (n) =nXp=11n(T (p − 1) + T (n − p)) + n − 1Each possible pivot p is selected with equal probability. Thenumber of comparisons needed to do the partition is n − 1.We will need one useful fact about the Harmonic numbersHn, namelyHn=nXi=11/i ≈ ln nIt is important to understand (1) where the recurrence relationcomes from and (2) how the log comes out from thesummation. The rest is just messy algebra.T (n) =nXp=11n(T (p − 1) + T (n − p)) + n − 1T (n) =2nnXp=1T (p − 1) + n − 1nT (n) = 2nXp=1T (p − 1) + n(n − 1) multiply by n(n−1)T (n−1) = 2n−1Xp=1T (p−1)+(n−1)(n−2) apply to n-1nT (n) − (n − 1)T (n − 1) = 2T (n − 1) + 2(n − 1)rearranging the terms give us:T (n)n + 1=T (n − 1)n+2(n − 1)n(n + 1)substituting an= A(n)/(n + 1) givesan= an−1+2(n − 1)n(n + 1)=nXi=12(i − 1)i(i + 1)an≈ 2nXi=11(i + 1)≈ 2 ln nWe are really interested in A(n), soA(n) = (n + 1)an≈ 2(n + 1) ln n ≈ 1.38n lg nPick a Better PivotHaving the worst case occur when they are sorted or almostsorted is very bad, since that is likely to be the case in certainapplications.To eliminate this problem, pick a better pivot:1. Use the middle element of the subarray as pivot.2. Use a random element of the array as the pivot.3. Perhaps best of all, take the median of three elements(first, last, middle) as the pivot. Why should we usemedian instead of the mean?Whichever of these three rules we use, the worst case remainsO(n2).Is Quicksort really faster than Heapsort?Since Heapsort is Θ(n lg n) and selection sort is Θ(n2), thereis no debate about which will be better for decent-sized files.When Quicksort is implemented well, it is typically 2-3 timesfaster than mergesort or heapsort.The primary reason is that the operations in the innermostloop are simpler.Since the difference between the two programs will be limitedto a multiplicative constant factor, the details of how youprogram each algorithm will make a big difference.Randomized QuicksortSuppose you are writing a sorting program, to run on datagiven to you by your worst enemy. Quicksort is good onaverage, but bad on certain worst-case instances.If you used Quicksort, what kind of data would your enemygive you to run it on? Exactly the worst-case instance, tomake you look bad.But instead of picking the median of three or the first elementas pivot, suppose you picked the pivot element at random.Now your enemy cannot design a worst-case instance to
View Full Document
Unlocking...