Lecture 38OutlineSortingSelection Sort 1Selection Sort 2Selection Sort 3Selection Sort 4Selection Sort 5Analysis of Selection Sort 1Analysis of Selection Sort 2Selection Sort ImplementationIn-class Exercise: Empirical Confirmation 1In-class Exercise: Empirical Confirmation 2Insertion Sort 1Insertion Sort 2Insertion Sort 3Insertion Sort 4In-class ExerciseMonday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 1Lecture 38Log into Linux. Copy files on csserver from /home/hwang/cs215/lecture38/*.* into a subdirectory.Reminder: Project 7 and Homework 9 due next Monday.Questions?Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 2OutlineSortingSelection sortInsertion sortMore algorithm analysisMonday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 3SortingApplications 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. We will look at a couple of "slow" algorithms today and will look at a couple of "fast" algorithms next week.Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 4Selection SortUnlike radix sort, these algorithms will be "in-place", meaning no other data structures will be involved.One way to sort is based on the following idea: For each position in the vector, find the element that belongs in that position (i.e., select it) and put it there. This is called selection sort.We choose to select the smallest value so the pass numbers and indexing match up. (The textbook selects the largest value.)Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 5Selection SortCall each time go through the vector elements a pass. Count passes from 0.Pass 0: Find smallest element in range [0, n), then place it in v[0].Of course, need to save the element currently in v[0], so swap it with the smallest element.Pass 1: Find smallest element in range [1, n), then swap it with v[1].Pass 2: Find smallest element in range [2, n), then swap it with v[2]....Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 6Selection SortHere is an example (circled number is the smallest value, sorted part is shaded):Note that when the second to last position gets its correct value, the last position does to. So there are n-1 passes and last placed is v[n-2].[0][1][2][3][4]50204075352050407535203540755020354075502035405075Pass 0Pass 1Pass 2 Pass 3Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 7Selection SortHow do we find the smallest element in a range?Assume that the first element is the smallest and look at the rest. When a smaller element is found, it becomes the smallest element.So for each pass, v[pass] is the first element and we search from v[pass+1] to v[n-1].Put this together into a function SelectionSort.Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 8Selection SortThe SelectionSort function receives and passes back a vector v. The algorithm is:1. If vector is empty, return2. For pass from 0 to v.size( )-2 by 1 2.1 Initialize smallest to v[pass] 2.2 Initialize indexOfSmallest to pass 2.3 For j from pass+1 to v.size( )-1 by 1 2.3.1 If v[j] is less than smallest 2.3.1.1 Set smallest to v[j] 2.3.1.2 Set indexOfSmallest to j 2.4 Set v[indexOfSmallest] to v[pass] 2.5 Set v[pass] to smallestMonday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 9Analysis of Selection SortDevelop T(n) for SelectionSort:Step # # of executions1 12 n2.1 n-12.2 n-12.3 n + (n-1) + (n-2) + ... + 2 + 12.3.1 (n-1) + (n-2) + ... + 2 + 12.3.1.1 (n-1) + (n-2) + ... + 2 + 12.3.1.2 (n-1) + (n-2) + ... + 2 + 12.4 n-12.5 n-1Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 10Analysis of Selection SortThe major term of T(n) is n2, so selection sort is an O(n2) algorithm.Another way of thinking about this is that searching an unorder list for the smallest value is an O(n) algorithm and selection sort uses this algorithm O(n) times, so the algorithm must be at least O(n2).Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 11Selection Sort ImplementationExamine the files sort-examples.cpp and sort.h containing a driver program and the SelectionSort function, respectively.SelectionSort is a template function for vectors that requires that type parameter T have an operator< defined.The driver program asks the user to enter numbers for a vector, then calls SelectionSort to sort them.Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 12In-class Exercise:Empirical ConfirmationTo empirically confirm what the analysis shows, we will instrument the SelectionSort code to count the number of algorithm steps that are executed for actual data.In order for both the function and the main program to have access to an integer counter selectionCount, we will declare it as global data in sort.h, outside any function definition.Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 13In-class Exercise:Empirical ConfirmationEvery time a line of the program is executed, selectionCount is incremented. Make sure you understand when to count something. For example, an if-header is always executed whether or not its body is executed, so it must be counted outside its body. On the other hand, a for-header is executed each time the body is executed, so it must be counted inside its body.After instrumentation has been completed, uncomment the line in the main program that prints out the selectionCount's valueMonday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 14Insertion SortHere is a different idea for sort: Assume the first element is in order. For each element after the first, "insert" it into its correct place with respect to the previously sorted elements before it. This method is called insertion sort.Of course, "insertion" requires that the values that come after the element being inserted be moved to make room for the insertion. Since they are already in order, we just "slide" them one position to the right.Monday, November 22 CS 215 Fundamentals of Programming II - Lecture 38 15Insertion SortThis time count the passes starting at 1Pass 1: Insert v[1] with respect to range [0, 0]Pass 2: Insert v[2] with
View Full Document
Unlocking...