Class Notes
(811,705)

Canada
(494,883)

Simon Fraser University
(12,088)

Computing Science
(220)

CMPT 225
(60)

John Edgar
(28)

Lecture 5

# CMPT 225 Week 5 Lecture 1

Unlock Document

Computing Science

CMPT 225

John Edgar

Summer

Description

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