CSCI 1030U Lecture Notes - Lecture 32: Insertion Sort
23 Nov 2017
School
Department
Course
Professor
Document Summary
Purpose: to sort a list by comparing left and right. Pseudocode: for j = 2 to length[a] do. We"ll assume first element is already sorted. we"ll start from the second element. Compare checkthis with checkthis-1 (let"s call this checkthis"). index of first element will be (checkthis-1) If checkthis is smaller than checkthis-1 (something on the right is smaller than the left), means it needs to be arranged. swap the two positions ( a[i+1] = a[i] ) Continue doing so until you hit the very left element ( i = i-1 : binary search. Pseudocode: if start > end then middle = ((end - start) / 2) + start if x = a[middle] then. Return binary-search(x, a, start, middle - 1) else. Return binary-search(x, a, middle + 1, end) General approach: (e. g we have [1,2,3,4,5] and we"re finding 6) Start from the middle (so we start from (5+1)/2 = 3. index 3 = the number 4)
