notes.md 1.5 KB
Newer Older
michael lundquist's avatar
michael lundquist committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 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 re-order 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
-