CSC148H5 Lecture Notes - Lecture 30: Binary Tree, The Algorithm, Quicksort
27 Mar 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) Lecture 30: big oh 3 and sorting def f3(t): if not t: return [t. key] + f3(t. left) + f3(t. right) return [] Big oh worst-case time complexity for this function : o() Unlike our previous examples last week, this current one is recursive. Two questions: what is the purpose of this function? f3 returns a list of keys from binary tree t in preorder, the code if o() Return the index of the smallest item in l[i:] smallest_index = i for j in range(i+1, len(l)): return smallest_index if l[j] < l[smallest_index]: smallest_index = j def find_min(l, i): def selection_sort(l): Sort the elements of l in non-descending order. for i in range(len(l) - 1): smallest_index = find_min(l, i) Selection sort: keep choosing the smallest element and swapping it into place. Move l[i] to where it belongs in l[:i}. v = l[i] while i > 0 and l[i-1] > v:
