CP104 Lecture Notes - Lecture 10: Merge Sort, Bubble Sort, Insertion Sort
hayjayshay and 38575 others unlocked
2
CP104 Full Course Notes
Verified Note
2 documents
Document Summary
# imports from math import log from bst_linked import bst class sorts: Uses class attribute "swaps" to determine how many times elements are swapped by the class. Use: sorts. swaps = 0 swaps = 0 # tracks swaps performed. Sorts an array using the selection sort algorithm. Preconditions: a - a python list of comparable elements (?) Contents of a are sorted. n = len(a) i = 0 while i < n: # walk through entire array m = i j = i + 1 while j < n: # find smallest value in unsorted part of array if a[m] > a[j]: # track smallest value so far m = j j += 1 if m != i: Sorts. _swap(a, m, i) i = i + 1 return. Sorts an array using the insertion sort algorithm. Contents of a are sorted. n = len(a) i = 1 while i < n: