Post-class 06/03

1 files changed, 245 insertions, 0 deletions

diff --git a/06-03.md b/06-03.md
new file mode 100644
index 0000000..68b42e7
--- /dev/null
+++ b/06-03.md
@@ -0,0 +1,245 @@
+[\<- 06/01](06-01.md)
+
+---
+
+## Heap Sort
+
+- An improved version of Selection sort
+- How it works?
+	- Build a max-heap (O(nlog(n)))
+	- Select the largest element based on the heap and swap it with the last element in the unsorted list, and reheap (O(nlog(n)))
+	- Partitioned array: left side is an unsorted heap, right side is sorted
+	- total O(nlog(n)) (much faster than O(n^2))
+	- theoretically the fastest algorithm
+
+- Example: 32, 78, 45, 8, 56, 23
+
+|Heap          |to be inserted|to be inserted|to be inserted|to be inserted|to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|32            |78            |45            |8             |56            |23            |
+
+- Insert 78
+
+|Heap          |Heap          |to be inserted|to be inserted|to be inserted|to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|32            |78            |45            |8             |56            |23            |
+
+- To maintain the heap, swap 32 and 78
+
+|Heap          |Heap          |to be inserted|to be inserted|to be inserted|to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |32            |45            |8             |56            |23            |
+
+- Insert 45
+
+|Heap          |Heap          |Heap          |to be inserted|to be inserted|to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |32            |45            |8             |56            |23            |
+
+- Insert 8
+
+|Heap          |Heap          |Heap          |Heap          |to be inserted|to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |32            |45            |8             |56            |23            |
+
+- Insert 56
+
+|Heap          |Heap          |Heap          |Heap          |Heap          |to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |32            |45            |8             |56            |23            |
+
+- Swap 32 and 56
+
+|Heap          |Heap          |Heap          |Heap          |Heap          |to be inserted|
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |56            |45            |8             |32            |23            |
+
+- Insert 23
+
+|Heap          |Heap          |Heap          |Heap          |Heap          |Heap          |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|78            |56            |45            |8             |32            |23            |
+
+- Now the heap has been created, but we still need to sort it
+- Swap 23 and 56
+
+|Heap          |Heap          |Heap          |Heap          |Heap          |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|23            |56            |45            |8             |32            |78            |
+
+- Reheap down to get
+
+|Heap          |Heap          |Heap          |Heap          |Heap          |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|56            |32            |45            |8             |23            |78            |
+
+- Swap 56 and 23
+
+|Heap          |Heap          |Heap          |Heap          |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|23            |32            |45            |8             |56            |78            |
+
+- Reheap Down
+
+|Heap          |Heap          |Heap          |Heap          |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|45            |32            |23            |8             |56            |78            |
+
+- Swap 45 and 8
+
+|Heap          |Heap          |Heap          |Sorted        |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|8             |32            |23            |45            |56            |78            |
+
+- Reheap Down
+
+|Heap          |Heap          |Heap          |Sorted        |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|32            |8             |23            |45            |56            |78            |
+
+- Swap 32 and 23
+
+|Heap          |Heap          |Sorted        |Sorted        |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|23            |8             |32            |45            |56            |78            |
+
+- Reheap Down (same)
+- Swap 23 and 8
+
+|Heap          |Sorted        |Sorted        |Sorted        |Sorted        |Sorted        |
+|--------------|--------------|--------------|--------------|--------------|--------------|
+|8             |23            |32            |45            |56            |78            |
+
+- Done!
+
+- Is it stable?
+	- No (too much swapping to easily predict where things will be)
+		- This is the only downside of Heap Sort
+	- 78, 56, 32, **32**, 8, 23, 45
+
+- Big O
+	- Worst case: O(nlog(n))
+	- Best case: O(nlog(n))
+	- Average case: O(nlog(n))
+
+- Space overhead? O(1)
+
+## Shell Sort
+
+- An improved version of the insertion sort in which **diminishing partitions** are used to sort the data
+
+- How does it work?
+	- A list of N elements is divided into **K segments**, where K is known as the increment
+	- For each segment, do insertion sort
+	- Reduce the value of K and repeat the process, until K=1
+
+### Demonstration
+
+![demonstration](06-03_img1.png)
+
+- We do insertion sort on each segment
+
+### Example
+
+- 77, 62, 14, 9, 30, 21, 80, 25, 70, 55
+- We set k= 5, 3, 1 progressively
+
+|77|62|14|9 |30|21|80|25|70|55|
+|--|--|--|--|--|--|--|--|--|--|
+
+- Initial Sub-Arrays
+	- 77, 21
+	- 62, 80
+	- 14, 25
+	- 9, 70
+	- 30, 55
+- After sorting the segments, we get
+	- 21, 77
+	- 62, 80
+	- 14, 25
+	- 9, 70
+	- 30, 55
+
+|21|62|14|9 |30|77|80|25|70|55|
+|--|--|--|--|--|--|--|--|--|--|
+
+- Now, k=3, the new sub-arrays are
+	- 21, 9, 80, 55
+	- 62, 30, 25
+	- 14, 77, 70
+- After sorting the segments, we get
+	- 9, 21, 55, 80
+	- 25, 30, 62
+	- 14, 70, 77
+
+|9 |25|14|21|30|70|55|62|77|80|
+|--|--|--|--|--|--|--|--|--|--|
+
+- Now k=1, so the new sub-arrays will be length 1, and we will effectively just be doing an insertion sort
+	- This will actually be pretty fast, since by this point the array is nearly sorted
+
+### Code
+
+```
+void shellSort(int a[], int n){
+	int i, j, temp, k;
+
+	foreach value of k do{
+		for(i=k; i<n; i+=k){
+			temp = a[i];
+			for(j = i-k; j>=0 && temp<a[j]; j-=k){
+				a[j+k] = a[j];
+			}
+			a[j+k] = temp;
+		}
+	}
+}
+```
+
+- Notice that the code inside the for loop is just insertion sort
+
+- How to choose K?
+	- Prime numbers
+	- A power of 2 minus 1 (i.e. k = 2^i - 1)
+	- Fibonacci series
+
+- Is it stable?
+	- No
+	- 5 4 **4** 2 3 6
+
+- Big O
+	- Worst case - depends, O(n^(3/2)) if right k sequence chosen
+	- Average case - depends, O(n^(4/3)) (as above)
+	- Best case - O(nlog(n))
+
+- Space Overhead O(1)
+
+### Additional Notes
+
+- Best-case Big-O analysis:
+	- comparisons =
+		- n, for 1 sort with elements 1-apart (last step)
+		- \+ 3 * n/3, for 3 sorts with elements 3-apart (next-to-last step)
+		- \+ 7 * n/7, for 7 sorts with elements 7-apart
+		- \+ 15 * n/15, for 15 sorts with elements 15-apart
+
+- Each term is n. The question is how many terms are there? The number of terms is the value k such that (2^i - 1)\<n; So i\<log(n+1), meaning that the sorting time in the best case is less than n * log(n+1) = O(n\*log(n))
+
+### Summary
+
+- The method starts by sorting pairs of elements **far apart from each other**, then **progressively reducing the gap** between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange
+
+## Tree Sort
+
+- Two steps:
+	- Insert each value from the array into a binary search tree
+	- Traverse the binary search tree in order and transfer the data back into the array
+
+- Worst case: O(n^2) if BST, O(nlog(n)) if AVL
+- Average case: O(nlog(n))
+- Best case: O(nlog(n))
+
+- Space overhead? O(n) (high!)
+	- You need to build a binary tree for this sort
+
+- It is stable!