Question? Leave a message!




Quicksort

Quicksort
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 © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Quicksort 2 Outline In this topic we will look at quicksort: – The idea behind the algorithm – The run time and worstcase scenario – Strategy for avoiding the worstcase: medianofthree – Implementing quicksort in place – ExamplesQuicksort 3 7.6 Strategy We have seen two Q(n ln(n)) sorting algorithms: – Heap sort which allows inplace 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 sublists and sorts them The larger problem is split into two subproblems 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 Runtime analysis Like merge sort, we can either: – Apply insertion sort if the size of the sublist is sufficiently small, or – Sort the sublists using quicksort In the best case, the list will be split into two approximately equal sublists, 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 luckyQuicksort 7 7.6.2 Worstcase 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 Worstcase 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 Medianofthree 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 Medianofthree Sorting the elements based on 44 results in two sublists, each of which must be sorted (again, using quicksort) Select the 26 to partition the first sublist: Select 81 to partition the second sublist:Quicksort 11 7.6.3 Medianofthree 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 medianofthree, this will, on average, divide the n items into two sets of size 5/16 n and 11/16 n – Medianofthree 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 Medianofthree Recall that merge sort always divides a list into two equal halves: 1  ln  2  1.8499 – The medianofthree 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 Medianofthree 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 medianofthree – 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 medianofthree, 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 nearequal arrays Can we implement quicksort in placeQuicksort 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 straightforward template typename Type void quicksort( Type array, int first, int last ) if ( last first = N ) insertionsort( array, first, last ); else Type pivot = findpivot( array, first, last ); int low = findnext( pivot, array, first + 1 ); int high = findprevious( pivot, array, last 2 ); while ( low high ) std::swap( arraylow, arrayhigh ); low = findnext( pivot, array, low + 1 ); high = findprevious( pivot, array, high 1 ); arraylast – 1 = arraylow; arraylow = pivot; quicksort( array, first, low ); quicksort( array, high, last ); Quicksort 22 7.6.5 Quicksort example Consider the following unsorted array of 25 entries 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 We will call insertion sort if the list being sorted of size N = 6 or lessQuicksort 23 7.6.5 Quicksort example We call quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 quicksort( array, 0, 25 ) Quicksort 24 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 First, 25 – 0 6, so find the midpoint and the pivot midpoint = (0 + 25)/2; // == 12 quicksort( array, 0, 25 ) Quicksort 25 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 7 51 88 97 First, 25 – 0 6, so find the midpoint and the pivot midpoint = (0 + 25)/2; // == 12 pivot = 57; quicksort( array, 0, 25 ) Quicksort 26 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 7 51 88 97 Starting from the front and back: – Find the next element greater than the pivot – The last element less than the pivot pivot = 57; quicksort( array, 0, 25 ) Quicksort 27 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 7 51 88 97 Searching forward and backward: low = 1; high = 21; pivot = 57; quicksort( array, 0, 25 ) Quicksort 28 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 61 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 7 77 88 97 Searching forward and backward: low = 1; high = 21; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 29 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 61 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 7 77 88 97 Continue searching low = 4; high = 20; pivot = 57; quicksort( array, 0, 25 ) Quicksort 30 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 61 77 88 97 Continue searching low = 4; high = 20; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 31 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 73 23 95 3 89 37 62 99 17 32 94 28 15 55 61 77 88 97 Continue searching low = 6; high = 19; pivot = 57; quicksort( array, 0, 25 ) Quicksort 32 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 95 3 89 37 62 99 17 32 94 28 15 73 61 77 88 97 Continue searching low = 6; high = 19; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 33 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 95 3 89 37 62 99 17 32 94 28 15 73 61 77 88 97 Continue searching low = 8; high = 18; pivot = 57; quicksort( array, 0, 25 ) Quicksort 34 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 89 37 62 99 17 32 94 28 95 73 61 77 88 97 Continue searching low = 8; high = 18; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 35 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 89 37 62 99 17 32 94 28 95 73 61 77 88 97 Continue searching low = 10; high = 17; pivot = 57; quicksort( array, 0, 25 ) Quicksort 36 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 62 99 17 32 94 89 95 73 61 77 88 97 Continue searching low = 10; high = 17; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 37 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 62 99 17 32 94 89 95 73 61 77 88 97 Continue searching low = 12; high = 15; pivot = 57; quicksort( array, 0, 25 ) Quicksort 38 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 99 17 62 94 89 95 73 61 77 88 97 Continue searching low = 12; high = 15; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 39 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 99 17 62 94 89 95 73 61 77 88 97 Continue searching low = 13; high = 14; pivot = 57; quicksort( array, 0, 25 ) Quicksort 40 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 99 62 94 89 95 73 61 77 88 97 Continue searching low = 13; high = 14; Swap them pivot = 57; quicksort( array, 0, 25 ) Quicksort 41 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 99 62 94 89 95 73 61 77 88 97 Continue searching low = 14; high = 13; Now, low high, so we stop pivot = 57; quicksort( array, 0, 25 ) Quicksort 42 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 14; high = 13; Now, low high, so we stop pivot = 57; quicksort( array, 0, 25 ) Quicksort 43 7.6.5 Quicksort example We are calling quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 57 62 94 89 95 73 61 77 88 97 99 We now begin calling quicksort recursively on the first half quicksort( array, 0, 14 ); quicksort( array, 0, 25 ) Quicksort 44 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 0 6, so find the midpoint and the pivot midpoint = (0 + 14)/2; // == 7 quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 45 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 17 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 0 6, so find the midpoint and the pivot midpoint = (0 + 14)/2; // == 7 pivot = 17 quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 46 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 0 6, so find the midpoint and the pivot midpoint = (0 + 14)/2; // == 7 pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 47 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Starting from the front and back: – Find the next element greater than the pivot – The last element less than the pivot pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 48 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 51 49 35 7 48 55 23 15 3 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 1; high = 9; pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 49 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 49 35 7 48 55 23 15 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 1; high = 9; Swap them pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 50 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 49 35 7 48 55 23 15 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 2; high = 8; pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 51 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 35 7 48 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 2; high = 8; Swap them pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 52 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 35 7 48 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 3; high = 4; pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 53 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 7 35 48 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 3; high = 4; Swap them pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 54 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 7 35 48 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 4; high = 3; Now, low high, so we stop pivot = 17; quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 55 7.6.5 Quicksort example We are executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 7 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 We continue calling quicksort recursively quicksort( array, 0, 4 ); quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 56 7.6.5 Quicksort example We are executing quicksort( array, 0, 4 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 7 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 Now, 4 – 0 ≤ 6, so find we call insertion sort quicksort( array, 0, 4 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 57 7.6.5 Quicksort example Insertion sort just sorts the entries from 0 to 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 3 15 7 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 insertionsort( array, 0, 4 ) quicksort( array, 0, 4 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 58 7.6.5 Quicksort example Insertion sort just sorts the entries from 0 to 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 – This function call completes and so we exit insertionsort( array, 0, 4 ) quicksort( array, 0, 4 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 59 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 quicksort( array, 0, 4 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 60 7.6.5 Quicksort example We are back to executing quicksort( array, 0, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 We continue calling quicksort recursively on the second half quicksort( array, 0, 4 ); quicksort( array, 5, 14 ); quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 61 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 5 6, so find the midpoint and the pivot midpoint = (5 + 14)/2; // == 9 quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 62 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 48 55 23 49 51 28 37 32 35 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 5 6, so find the midpoint and the pivot midpoint = (5 + 14)/2; // == 9 pivot = 48 quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 63 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 First, 14 – 5 6, so find the midpoint and the pivot midpoint = (5 + 14)/2; // == 9 pivot = 48 quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 64 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Starting from the front and back: – Find the next element greater than the pivot – The last element less than the pivot pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 65 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 55 23 49 51 28 37 32 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 6; high = 12; pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 66 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 49 51 28 37 55 57 62 94 89 95 73 61 77 88 97 99 Searching forward and backward: low = 6; high = 12; Swap them pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 67 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 49 51 28 37 55 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 68 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 51 28 49 55 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; Swap them pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 69 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 51 28 49 55 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 70 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 51 49 55 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; Swap them pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 71 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 51 49 55 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; Now, low high, so we stop pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 72 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 Continue searching low = 8; high = 11; Now, low high, so we stop pivot = 48; quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 73 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 We now begin calling quicksort recursively on the first half quicksort( array, 5, 10 ); quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 74 7.6.5 Quicksort example We now are calling quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 We now begin calling quicksort recursively quicksort( array, 5, 10 ); quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 75 7.6.5 Quicksort example We are executing quicksort( array, 5, 10 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 Now, 10 – 5 ≤ 6, so find we call insertion sort quicksort( array, 5, 10 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 76 7.6.5 Quicksort example Insertion sort just sorts the entries from 5 to 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 35 32 23 37 28 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 insertionsort( array, 5, 10 ) quicksort( array, 5, 10 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 77 7.6.5 Quicksort example Insertion sort just sorts the entries from 5 to 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 – This function call completes and so we exit insertionsort( array, 5, 10 ) quicksort( array, 5, 10 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 78 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 quicksort( array, 5, 10 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 79 7.6.5 Quicksort example We are back to executing quicksort( array, 5, 14 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 We continue calling quicksort recursively on the second half quicksort( array, 5, 10 ); quicksort( array, 6, 14 ); quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 80 7.6.5 Quicksort example We are executing quicksort( array, 11, 15 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 Now, 15 – 11 ≤ 6, so find we call insertion sort quicksort( array, 6, 14 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 81 7.6.5 Quicksort example Insertion sort just sorts the entries from 11 to 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 55 51 57 62 94 89 95 73 61 77 88 97 99 insertionsort( array, 11, 14 ) quicksort( array, 11, 14 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 82 7.6.5 Quicksort example Insertion sort just sorts the entries from 11 to 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 – This function call completes and so we exit insertionsort( array, 11, 14 ) quicksort( array, 11, 14 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 83 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 quicksort( array, 11, 14 ) quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 84 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 quicksort( array, 5, 14 ) quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 85 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 quicksort( array, 0, 14 ) quicksort( array, 0, 25 ) Quicksort 86 7.6.5 Quicksort example We are back to executing quicksort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 We continue calling quicksort recursively on the second half quicksort( array, 0, 14 ); quicksort( array, 15, 25 ); quicksort( array, 0, 25 ) Quicksort 87 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 62 94 89 95 73 61 77 88 97 99 First, 25 – 15 6, so find the midpoint and the pivot midpoint = (15 + 25)/2; // == 20 quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 88 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 94 89 95 73 99 77 88 97 First, 25 – 15 6, so find the midpoint and the pivot midpoint = (15 + 25)/2; // == 20 pivot = 62; quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 89 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 94 89 95 73 99 77 88 97 Searching forward and backward: low = 16; high = 15; Now, low high, so we stop pivot = 62; quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 90 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 Searching forward and backward: low = 16; high = 15; Now, low high, so we stop – Note, this is the worstcase scenario – The pivot is the second smallest element pivot = 62; quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 91 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 We continue calling quicksort recursively on the first half quicksort( array, 15, 16 ); quicksort( array, 15, 16 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 92 7.6.5 Quicksort example We are executing quicksort( array, 15, 16 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 Now, 16 – 15 ≤ 6, so find we call insertion sort quicksort( array, 15, 16 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 93 7.6.5 Quicksort example Insertion sort immediately returns 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 insertionsort( array, 15, 16 ) quicksort( array, 15, 16 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 94 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 quicksort( array, 15, 16 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 95 7.6.5 Quicksort example We are back to executing quicksort( array, 15, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 We continue calling quicksort recursively on the second half quicksort( array, 15, 16 ); quicksort( array, 17, 25 ); quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 96 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 First, 25 – 17 6, so find the midpoint and the pivot midpoint = (17 + 25)/2; // == 21 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 97 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 First, 25 – 17 6, so find the midpoint and the pivot midpoint = (17 + 25)/2; // == 21 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 98 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 89 95 73 99 77 88 97 94 First, 25 – 17 6, so find the midpoint and the pivot midpoint = (17 + 25)/2; // == 21 pivot = 89 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 99 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 95 73 99 94 88 97 First, 25 – 17 6, so find the midpoint and the pivot midpoint = (17 + 25)/2; // == 21 pivot = 89 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 100 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 95 73 99 94 88 97 Searching forward and backward: low = 18; high = 22; pivot = 89; quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 101 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 99 94 95 97 Searching forward and backward: low = 18; high = 22; Swap them pivot = 89; quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 102 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 99 94 95 97 Searching forward and backward: low = 20; high = 19; Now, low high, so we stop pivot = 89; quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 103 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 89 94 95 97 99 Searching forward and backward: low = 20; high = 19; Now, low high, so we stop pivot = 89; quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 104 7.6.5 Quicksort example We are now calling quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 89 94 95 97 99 We start by calling quicksort recursively on the first half quicksort( array, 17, 20 ); quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 105 7.6.5 Quicksort example We are now executing quicksort( array, 17, 20 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 89 94 95 97 99 Now, 4 – 0 ≤ 6, so find we call insertion sort quicksort( array, 17, 20 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 106 7.6.5 Quicksort example Insertion sort just sorts the entries from 17 to 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 77 88 73 89 94 95 97 99 insertionsort( array, 17, 20 ) quicksort( array, 17, 20 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 107 7.6.5 Quicksort example Insertion sort just sorts the entries from 17 to 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 – This function call completes and so we exit insertionsort( array, 17, 20 ) quicksort( array, 17, 20 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 108 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 17, 20 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 109 7.6.5 Quicksort example We are back to executing quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 110 7.6.5 Quicksort example We are back to executing quicksort( array, 17, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 We continue by calling quicksort on the second half quicksort( array, 17, 20 ); quicksort( array, 21, 25 ); quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 111 7.6.5 Quicksort example We are now calling quicksort( array, 21, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 Now, 25 – 21 ≤ 6, so find we call insertion sort quicksort( array, 21, 25 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 112 7.6.5 Quicksort example Insertion sort just sorts the entries from 21 to 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 insertionsort( array, 21, 25 ) quicksort( array, 21, 25 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 113 7.6.5 Quicksort example Insertion sort just sorts the entries from 21 to 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 – In this case, the subarray was already sorted – This function call completes and so we exit insertionsort( array, 21, 25 ) quicksort( array, 21, 25 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 114 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 21, 25 ) quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 115 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 17, 25 ) quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 116 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 15, 25 ) quicksort( array, 0, 25 ) Quicksort 117 7.6.5 Quicksort example This call to quicksort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 quicksort( array, 0, 25 ) Quicksort 118 7.6.5 Quicksort example We have now used quicksort to sort this array of 25 entries 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99Quicksort 119 7.6.5 Black Board Example Sort the following list using quicksort – Use insertion sort for any sublist of size 4 or less 0 1 2 3 4 5 6 7 8 9 10 34 15 65 59 68 42 40 80 50 65 23Quicksort 120 7.6.6 Memory Requirements The additional memory required is Q(ln(n)) – In ECE 222, you learned about the memory stack – Each recursive function call places its local variables, parameters, etc., on a stack • The depth of the recursion tree is Q(ln(n)) 2 – Unfortunately, if the run time is Q(n ), the memory use is Q(n)Quicksort 121 7.6.7 Runtime Summary To summarize all three Q(n ln(n)) algorithms Average Worstcase Average Worstcase Run Time Run Time Memory Memory HeapSort Q(n ln(n))Q(1) MergeSort Q(n ln(n))Q(n) 2 QuicksortQ(n ln(n))Q(n )Q(ln(n))Q(n)Quicksort 122 7.6.7 Further modifications Our implementation is by no means optimal: An excellent paper on quicksort was written by Jon L. Bentley and M. Douglas McIlroy: Engineering a Sort Function found in Software—Practice and Experience, Vol. 23(11), Nov 1993Quicksort 123 7.6.7 Further modifications They detail further suggestions: – Taking the median of three mediansofthree Expected ratio of 1:1.7292 Requires 52 more depth than merge sort Ratio will be 1:3.3304 or better 90 of the time • Better than the medianofseven but much easier to calculate • The median of nine would still require 46 more depth than merge sort x 23 F x 3 1 d 3x 2x  median of 3  0 2 3 2 3 f x 3 3x 2x 1 3x 2x 3x 1 x     median of medians 1 2 469 2 x f x dx 0.3664  median of medians  1280 0Quicksort 124 7.6.7 Further modifications As for the affect on runtime, the ratio of the recurrence relations is now closer to only 0.15 worse than using the median  469 811  T n T n T n n  median of medians  1280 1280   11  T n T n T n n  median   22   Tn  median of medians Tn  medianQuicksort 125 7.6.7 Further modifications They detail further suggestions: – Copy entries equal to the pivot to either end: • This requires more tracking of indices (using their notation): • After the pass, we have: • Copy the equal entries to the center and only recurs on either side – Other suggestions are made in the paper, as well…Quicksort 126 Summary This topic covered quicksort – On average faster than heap sort or merge sort – Uses a pivot to partition the objects – Using the median of three pivots is a reasonably means of finding the pivot – Average run time of Q(n ln(n)) and Q(ln(n)) memory 2 – Worst case run time of Q(n ) and Q(n) memoryQuicksort 127 References Wikipedia, http://en.wikipedia.org/wiki/Quicksort 1 Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, nd 2 Ed., Addison Wesley, 1998, §5.1, 2, 3. 2 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, p.1379 and §9.1. rd 3 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §7.1, p.2612. 4 Gruber, Holzer, and Ruepp, Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017