# notes 2_5_19
 last week:
 insertion sort
 2 loops, O(n^2) time
 linear search
## sorting
 selection sort:
 also O(n^2)
 works by iteratively finding the smallest element, and appending it to the sorted part.
 bubble sort:
 O(n^2)
 Iterate over array swapping elements if they're in the wrong order. Keep iterating over the array until the array is in order
 heap sort
 binary trees:
 the root of the heap is always the minimum (or max) in the tree
 every node should be smaller (or large) that its children, so when you pop from the heap, you need to reorder the heap
 Bucket sort
 number and size of buckets is important
 O(n) time
 large memory footprint
 Stably sort:
 When sorting an array of arrays, sort by the last element first, then second to last...
 Radix sort
 sort on least significant bit, then second significant bit... to most significant bit
 similar to stably sort
 when we do this, we can use strings or math
### assignment
 have a user input for choosing the algorithm
### Lab 1
 work on as a group
 implement Voting application's getWinner method
## Recursion
 the stack pushes and pops recursively
 Recursion steps:
 determine the base case
 determine the recursive case.
### Merge sort
 divide and conquer
 O(n log n)
### quick sort
 also divide and conquer
 finds a pivot point, then does merge sort
 the worst case pivot is one that always pivots on 1
## exercises
 binary search

 english ruler
