Quicksort example ppt

quicksort average case analysis ppt and quicksort ppt presentation
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Quicksort Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Quicksort 3 7.6 Strategy We have seen two Q(n ln(n)) sorting algorithms: – Heap sort which allows in-place sorting, and – Merge sort which is faster but requires more memory We will now look at a recursive algorithm which may be done almost in place but which is faster than heap sort – Use an object in the array (a pivot) to divide the two – Average case:Q(n ln(n)) time and Q(ln(n)) memory 2 – Worst case:Q(n ) time and Q(n) memory We will look at strategies for avoiding the worst caseQuicksort 4 7.6.1 Quicksort Merge sort splits the array sub-lists and sorts them The larger problem is split into two sub-problems based on location in the array Consider the following alternative: – Chose an object in the array and partition the remaining objects into two groups relative to the chosen entryQuicksort 5 7.6.1 Quicksort For example, given 80 38 95 84 66 10 79 44 26 87 96 12 43 81 3 we can select the middle entry, 44, and sort the remaining entries into two groups, those less than 44 and those greater than 44: 38 10 26 12 43 3 44 80 95 84 66 79 87 96 81 Notice that 44 is now in the correct location if the list was sorted – Proceed by applying the algorithm to the first six and last eight entriesQuicksort 6 7.6.1 Run-time analysis Like merge sort, we can either: – Apply insertion sort if the size of the sub-list is sufficiently small, or – Sort the sub-lists using quicksort In the best case, the list will be split into two approximately equal sub-lists, and thus, the run time could be very similar to that of merge sort: Q(n ln(n)) What happens if we don’t get that lucky?Quicksort 7 7.6.2 Worst-case scenario Suppose we choose the first element as our pivot and we try ordering a sorted list: 80 38 95 84 66 10 79 2 26 87 96 12 43 81 3 Using 2, we partition into 2 80 38 95 84 66 10 79 26 87 96 12 43 81 3 We still have to sort a list of size n – 1 2 The run time is T(n) = T(n – 1) + Q(n) = Q(n ) 2 – Thus, the run time drops from n ln(n) to nQuicksort 8 7.6.2 Worst-case scenario Our goal is to choose the median element in the list as our pivot: 80 38 95 84 66 10 79 2 26 87 96 12 43 81 3 Unfortunately, it’s difficult to find Alternate strategy: take the median of a subset of entries – For example, take the median of the first, middle, and last entriesQuicksort 9 7.6.3 Median-of-three It is difficult to find the median so consider another strategy: – Choose the median of the first, middle, and last entries in the list This will usually give a better approximation of the actual medianQuicksort 10 7.6.3 Median-of-three Sorting the elements based on 44 results in two sub-lists, each of which must be sorted (again, using quicksort) Select the 26 to partition the first sub-list: Select 81 to partition the second sub-list:Quicksort 11 7.6.3 Median-of-three If we choose a random pivot, this will, on average, divide a set of n items into two sets of size 1/4 n and 3/4 n – 90 % of the time the width will have a ratio 1:19 or better Choosing the median-of-three, this will, on average, divide the n items into two sets of size 5/16 n and 11/16 n – Median-of-three helps speed the algorithm 2 31 x  – This requires order statistics: 2 3x 1 2 5 2 x 6x 1 x dx 0.3125   3xx 1  16 0 – Ratio 1:2.2 on average – 90 % of the time, the width will have a ratio of 1:6.388 or betterQuicksort 12 7.6.3 Median-of-three Recall that merge sort always divides a list into two equal halves: 1  ln  2  1.8499 – The median-of-three will require or 85 % more recursive 11  steps ln  16  1  ln  2  – A single random pivot will require  2.4094 or 141 % more 3  recursive steps ln  4 Quicksort 13 7.6.3 Median-of-three Question: what is the affect on run time? 13  – Surprisingly, not so much T n T n T n n  random pivot  44 – Here we see the ratios of the   recurrence relations for large  5 11  values of n T n T n T n n  median of 3   16 16   11  T n T n T n n  median  Tn  22 random pivot   Tn  median Tn  median of 3 Tn  medianQuicksort 14 7.6.4 Implementation If we choose to allocate memory for an additional array, we can implement the partitioning by copying elements either to the front or the back of the additional array Finally, we would place the pivot into the resulting holeQuicksort 15 7.6.4 Implementation For example, consider the following: – 57 is the median-of-three – we go through the remaining elements, assigning them either to the front or the back of the second arrayQuicksort 16 7.6.4 Implementation Once we are finished, we copy the median-of-three, 57, into the resulting holeQuicksort 17 7.6.4 Implementation Note, however, we can do a better job with merge sort, it always divides the numbers being sorted into two equal or near-equal arrays Can we implement quicksort in place?Quicksort 18 7.6.5 Implementation First, we have already examined the first, middle, and last entries and chosen the median of these to be the pivot In addition, we can: – move the smallest entry to the first entry – move the largest entry to the middle entryQuicksort 19 7.6.5 Implementation Next, recall that our goal is to partition all remaining elements based on whether they are smaller than or greater than the pivot We will find two entries: – One larger than the pivot (staring from the front) – One smaller than the pivot (starting from the back) which are out of order and then swap themQuicksort 20 7.6.5 Implementation Continue doing so until the appropriate entries you find are actually in order The index to the larger entry we found would be the first large entry in the list (as seen from the left) Therefore, we could move this entry into the last entry of the list We can fill this spot with the pivotQuicksort 21 7.6.5 Implementation The implementation is straight-forward template typename Type void quicksort( Type array, int first, int last ) if ( last - first = N ) insertion_sort( array, first, last ); else Type pivot = find_pivot( array, first, last ); int low = find_next( pivot, array, first + 1 ); int high = find_previous( pivot, array, last - 2 ); while ( low high ) std::swap( arraylow, arrayhigh ); low = find_next( pivot, array, low + 1 ); high = find_previous( pivot, array, high - 1 ); arraylast – 1 = arraylow; arraylow = pivot; quicksort( array, first, low ); quicksort( array, high, last );