CMPT 225 Lecture Notes - Lecture 5: Stack Overflow, Selection Sort, Binary Search Algorithm

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

// 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; 7 instructions in outer loop, evaluated n-1 times. 4 instructions, 1 run only some of the time. 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. First element is treated as sorted part of the array. 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.