Class Notes (811,705)
Canada (494,883)
CMPT 225 (60)
John Edgar (28)
Lecture 5

CMPT 225 Week 5 Lecture 1

3 Pages
Unlock Document

Computing Science
CMPT 225
John Edgar

Selection Sort void selectionSort(int arr[], int size) { // two loops: outer finds next smallest item for (int i = 0; i < size - 1; i++) { int smallest = i; for (int j = i + 1; j < size; j++) { // if find something smaller than smallest, make that new current val of smallest if (arr[j] < arr[smallest]) { smallest = j; } } temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp; } } Barometer instruction is evaluated n(n-1) times 7 instructions in outer loop, evaluated n-1 times Inner loop evaluated n(n-1)/2 times 4 instructions, 1 run only some of the time Makes roughly n(n-1)/2 comparisons, performs n-1 swaps. Not substantially affected by organization of output. Best case is close to worse case. Insertion Sort Divides array into sorted and unsorted parts. Sorted part of array is expanded one element at a time. Find correct place in sorted part to place 1st element in unsorted part Move elements after insertion point up one to make room In place sorting. First element is treated as sorted part of the array. Sorted sub array of size 1. Amount of work done actually does depend on order of contents of array. void insertionSort(int arr[], int size) { for (int i = 1; i < size; i++) { // runs n-1 times temp = arr[i]; int pos = i; while(pos > 0 && arr[pos-1] > temp) { // don't know how many times this will run arr[pos] = arr[pos-1]; // moves down array until we find insertion point pos--; } // insert current item arr[pos] = temp; } } Inner will run at least once for each the iterations of the outer loop, so at least n times. Max is i - 1 times for each iteration. So could be n*(n-1)/2. Would make that many moves and assignments in the worst case, unlike selection sort, which would do fewer moves. Best case: array already completely sorted. No moves required, just makes n comparisons. How do you tell if an array is sorted? Insertion sort can actually test this.Also a really good algorithm for something that is mostly sorted. Kind of terrible to use for anything else. Actually has some nice qualities, unlike bubble and selection sort. If random data is sorted, average case is probably closer to worse, around n*(n-1)/4 comparisons. Somewhat sorted data is closer to best case. But i
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.