Lecture 39OutlineSortingDivide and ConquerQuicksort 1Quicksort 2Quicksort 3Partition 1Partition 2Partition 3Partition 4Partition 5In-class ExerciseAnalysis of Quicksort 1Analysis of Quicksort 2Analysis of Quicksort 3Choosing a Pivot 1Choosing a Pivot 2Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 1Lecture 39Log into Linux. We will be adding code to files sort.h and sort-examples.cpp from last class. If you were absent, copy files on csserver from /home/hwang/cs215/lecture39/*.* into a subdirectory. They have the functions and calls, but no instrumentation.Reminder: Project 7 and Homework 9 due today. Project 8 and Homework 10 posted, both due next Monday, Dec. 6.Questions?Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 2OutlineMore SortingQuicksort - 2nd half of Section 13.2More algorithm analysisO(nlog2n) running timeWorst-case != average-caseMonday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 3SortingRecall: Applications often require data to be sorted. For a vector v with n elements this means the elements are arranged such thatv[0] v[1] ... v[n-2] v[n-1]There are lots of different algorithms. Last time we look at a couple of "slow", O(n2) algorithms. Today we will look at a "fast" algorithm.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 4Divide and ConquerOne class of recursive algorithms is called divide and conquer.The basic idea is to divide the problem in two or more approximately equal-sized subproblems, solve them directly or recursively, then combine the subproblem results into the result for the original problem.Section 13.2 covers two sorting algorithms, mergesort and quicksort that use this method. We will cover only quicksort.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 5QuicksortNote: the textbook presents a method for sorting arrays that uses pointer arithmetic. We will be sorting vectors, so we will be using indexes [first, last) to indicate the range to be sorted.One of the reasons that sorting algorithms like selection and insertion sort are so slow is that the exchanges do not move the elements very far. Quicksort attempts to speed this up by making the exchanges more effective.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 6QuicksortThe basic idea of quicksort is to arrange the elements of a vector range [first, last) into two "sublists" such that:values in lower sublist pivot value < values in higher sublistThen recursively apply this idea to each sublist until get to base cases of 0 or 1 elements in a sublist.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 7QuicksortThe Quicksort function itself receives and passes back a vector, v, and receives first and last indexes representing range [first, last). Its algorithm is:1. If last - first > 1 then // at least 2 elements 1.1 Partition the range [first, last) using Partition (v, first, last, pivotIndex) 1.2 Sort the left sublist using Quicksort (v, first, pivotIndex) 1.3 Sort the right sublist using Quicksort (v, pivotIndex+1, last)Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 8PartitionDividing the original vector range into the two sublists is encapsulated in the Partition function. This function receives and passes back a vector, v, and receives indexes first and last representing range [first, last). It passes back pivotIndex, the index where the pivot element is placed.The first step is to choose a pivot element. For ease of implementation, we will choose the first element of the range (i.e., v[first]).Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 9PartitionTo divide the range, we scan from the left end (using tooBigIndex) looking for an element that is greater than the pivot, and scan from the right end (using tooSmallIndex) looking an element that is less than or equal to the pivot, then swap them. The scanning and swapping continues until the indexes cross each other. When the indexes cross, tooSmallIndex is the index of the rightmost element that is less than or equal to the pivot element.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 10PartitionFinally, to place the pivot element (v[first]), it is swapped with the element at tooSmallIndex.The next slide shows an example of how this works for the first partition of an original call: Quicksort(v, 0, v.size());The green circled element is the pivot. The red circled elements are the ones found to be in the "wrong half" and are swapped. pivotIndex is set to the index where the pivot element is placed.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 11Partition40 20 10 80 60 50 7 30 100 90 70[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]v40 20 10 30 60 50 7 80 100 90 70v40 20 10 30 7 50 60 80 100 90 70v7 20 10 30 40 50 60 80 100 90 70vpivottooBigIndex3tooSmallIndex7tooBigIndex4tooSmallIndex6tooSmallIndex4tooBigIndex5pivotIndex4Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 12PartitionThe algorithm for Partition is as follows:1. Initialize pivot to v[first], tooBigIndex to first+1, and tooSmallIndex to last-12. While the indexes have not crossed 2.1 While tooBigIndex has not reached last and v[tooBigIndex] is less than or equal to the pivot 2.1.1 Increment tooBigIndex 2.2 While v[tooSmallIndex] is greater than the pivot 2.2.1 Decrement tooSmallIndex 2.3 If the indexes have not met or crossed then 2.3.1 Swap v[tooBigIndex] and v[tooSmallIndex]3. Set pivotIndex to tooSmallIndex4. Set v[first] to v[pivotIndex]5. Set v[pivotIndex] to pivotMonday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 13In-class ExerciseImplement Partition and Quicksort as a function templates in file sort.h. In addition, write QuicksortStart, a wrapper function template that receives and passes back a vector, v, (like the other sorting functions) and makes the original call to start the recursion: Quicksort (v, 0, v.size());In file sort-examples.cpp, add code in the main program to make a new copy of the data vector, call the QuicksortStart function, and print out the sorted vector.Monday, November 29 CS 215 Fundamentals of Programming II - Lecture 39 14Analysis of
View Full Document
Unlocking...