Algorithms

Elementary Sorts

What is the invariant?
Quicksort: last position of the pivot is its final position in the array; everything above pivot is larger, everything below the pivot is smaller
Pivot is always 1st (i.e. LIFO)
A or D?
Selection sort: everything to a certain point is in its final ordering
D
Insertion sort: at every iteration everything on the left is sorted + everything on the right is untouched
C
Merge sort
Top down: doing in chunks of 5
E is in groups of 5 sorted words
Bottom down:
B is sorted from data --> type and leaf --> swim
Chunks of values are sorted
Shellsort
F
sorts in strides
Picks elements that are 5 apart and swap if left is lower
At every 5 elements, you are in sorted order
Then you reduce the interval until you reach stride of 1

Lowest Common Ancestor