SortingWhy don't CS profs ever stop talking about sorting?!Applications of SortingConvex HullsHuffman CodesExample ProblemsQuicksortQuicksort WalkthroughPseudocodeSlide 10Best Case for QuicksortWorst Case for QuicksortIntuition: The Average CaseWhat have we shown?Quicksort in the real world…Average-case AnalysisComputing XijComputing E[X]Avoiding worst-caseUnderstanding the worst casePivot StrategiesRandomization TechniquesIs Quicksort really faster than Mergesort?Possible reasons for not choosing quicksortOptimizing QuicksortIs Linear Sorting Possible?Example Decision TreeHow big is the decision tree?HeapsDefinitionExample HeapAre these legal?Partial Order PropertyInsertion OperationHeap ConstructionHeapify ExampleHeap Extract MaxHeap SortNon-comparison Based SortingBucketsortSlide 42Real World DistributionsSorting•Importance of sorting•Quicksort•Lower bounds for comparison-based methods•Heapsort•Non-comparison based sortingWhy don't CS profs ever stop talking about sorting?!•Computers spend more time sorting than anything else, historically 25% on mainframes. •Sorting is the best studied problem in computer science, with a variety of different algorithms known. •Most of the interesting ideas we encounter in the course are taught in the context of sorting, such as divide-and-conquer, randomized algorithms, and lower bounds. You should have seen most of the algorithms - we willconcentrate on the analysisApplications of Sorting•Closest Pair•Element Uniqueness•Frequency Distribution•Selection of Kth largest element•Convex Hulls –See next slide!Convex HullsHuffman CodesIf you are trying to minimize the amount of space a text file is taking up, it is silly to assign each letter the same length (i.e. one byte) code. Example: e is more common than q, a is more common than z . If we were storing English text, we would want a and e to have shorter codes than q and z.Example Problemsa. You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. Find out who did not pay. b. You are given a list containing the title, author, call number and publisher of all the books in a school library and another list of 30 publishers. Find out how many of the books in the library were published by each of those 30 companies. c. You are given all the book checkout cards used in the campus library during the past year, each of which contains the name of the person who took out the book. Determine how many distinct people checked out at least one book.QuicksortAlthough mergesort is O( n log n ), it is difficult to implement on arrays since we need space to merge. In practice, Quicksort is the fastest sorting algorithm.Example: Pivot about 1017 12 6 23 19 8 5 10 - before 6 8 5 10 17 12 23 19 - after The pivot point is now in the correctly sorted position, and all other numbers are in the relative correct position, before or after.Quicksort Walkthrough 17 12 6 23 19 8 5 106 8 5 10 17 12 23 195 6 8 17 12 19 23 6 8 12 17 23 6 175 6 8 10 12 17 19 23PseudocodeSort(A) { Quicksort(A,1,n);}Quicksort(A, low, high) { if (low < high) { pivotLocation = Partition(A,low,high); Quicksort(A,low, pivotLocation - 1); Quicksort(A, pivotLocation+1, high); }}Pseudocodeint Partition(A,low,high) { pivot = A[high]; leftwall = low-1; for i = low to high-1 { if (A[i] < pivot) then { leftwall = leftwall+1; swap(A[i],A[leftwall]); } swap(A[high],A[leftwall+1]); } return leftwall+1;}Best Case for QuicksortWorst Case for QuicksortIntuition: The Average Case0 n/4 n/2 3n/4 nAnywhere in the middle half is a decent partition(3/4)h n = 1 => n = (4/3)hlog(n) = h log(4/3)h = log(n) / log(4/3) < 2 log(n)What have we shown?At most 2log(n) decent partitions suffices to sort an array of n elements.But if we just take arbitrary pivot points, how often will they, in fact, be decent?Since any number ranked between n/4 and 3n/4 would make a decent pivot, we get one half the time on average. Therefore, on average we will need 2 x 2log(n) = 4log(n) partitions to guarantee sorting.Quicksort in the real world…Average-case Analysis•Let X denote the random variable that represents the total number of comparisons performed•Let Xij = probability that the ith smallest element and jth smallest element are compared•E[X] = i=1 to n-1 j=i+1 to n XijComputing Xij•Observation–All comparisons are between a pivot element and another element–If an item k is chosen as pivot where i < k < j, then items i and j will not be compared•Xij = 2/(j-i+1)–Items i or j must be chosen as a pivot before any items in interval (i..j)Computing E[X]E[X] = i=1 to n-1 j=i+1 to n 2/(j-i+1) = i=1 to n-1 j=i+1 to n 2/(j-i+1) = i=1 to n-1 k=1 to n-i 2/(k+1) <= i=1 to n-1 2 Hn-i+1 <= i=1 to n-1 2 Hn = 2 (n-1)HnAvoiding worst-case•Understanding quicksort’s worst-case•Methods for avoiding it–Pivot strategies–RandomizationUnderstanding the worst caseA B D F H J KA B D F H JA B D F HA B D FA B D A BAThe worst case occur is a likely case for many applications.Pivot Strategies•Use the middle Element of the sub-array as the pivot.•Use the median element of (first, middle, last) to make sure to avoid any kind of pre-sorting. What is the worst-case performance for these pivot selection mechanisms?Randomization Techniques•Make chance of worst-case run time equally small for all inputs•Methods–Choose pivot element randomly from range [low..high]–Initially permute the arrayIs Quicksort really faster than Mergesort?Since Quicksort is (n log n) and Selection Sort is (n2), there isn’t any debate about which is faster.How can we compare two (n log n) algorithms to know which one is faster?Using the RAM model and the big Oh notation, we can't! If all of the algorithms are well implemented, Quicksort is at least 2-3 times faster than any of the others, but this only has to do with implementation details.Possible reasons for not choosing quicksort• What do you know about the input data?•Is the data already partially sorted?• Do we know the distribution of the keys?• Are your keys very long or hard to compare?• Is the range of possible keys very small?Optimizing QuicksortUsing randomization: guarantees never to never have worst-case time due to bad