03-17

Recursion and sorting yay reminder for steps in recursion

1. base case:
   1. empty
   2. 1 item
   3. etc.
   4. You get closer to the base case with each call
2. Recursive step
   1. Split into sub arrays
   2. call recursively to sort
3. Putting together the sub-solutions into 1 big solution from the returned values

sorting_case1() ~> doofusort()

// 1. Base case!
if arraysize <= 1 return array;

// 2. Recursive step
split:

sub1 = array[0]
sub2 = array[1::]
sol1 = sorting_case1(sub1)
sol2 = sorting_case1(sub2)
sortedarray = merge_in_order(sol1, sol2);
return sortedarray;

	

This abv algo has O(N) work for the # of splits and O(N) for the work for each split. So it’s $O(N^2)$.

for merge_in_order, we take two arrays of size N: [1 7 9] [2 4 10] You would compare the first top and bottom number, keeping track of the indices, call them i and j. if $arr1[i]<arr2[j]$, then we add 1 to the final array and increase i by one. repeat that until both i and j go thru their respective arrays.

sorting_case2() ~> much better sort: merge sort!

The only difference is now we will split the arrays in half instead of 1 element and the rest of the array.

The number of splits is wayyy better! in fact, instead of N splits, we have ${\log }_2(N)$ splits. e.g. [-10 7 -3 4 5 1 6 8] (initial) [-10 7 -3 4] [5 1 6 8] (1) [-10 7] [-3 4] [5 1] [6 8] (2) [-10] [7] [-3] [4] [5] [1] [6] [8] (3) Then we sort the pairs, sort those sorted pairs, etc. the sorting is the same as doofusort (merge_in_order) and that was $O(N)$

In total it’s $O(N{\log }_2(N))$

The similarity between BSTS and linked lists w/ merge sort and doofus sort is symmetry! BSTs and merge sorts are symmetrical.

Quick sort

1) If arraysize <= 1 return array
2) split ()
	pivot = array[j] where j is some random entry in array
	sub1 = entries < pivot
	sub2 = pivot
	sub3 = entries > pivot
	sol1 = sort_case3(sub1)
	sol3 = sort_case3(sub3)
	merge_in_order(sub1, pivot, sub2)
	

on average, sub1 and sub2 are roughly the same size, so it’s kinda split. It’s rarely the case where either sub1 or sub2 is empty (otherwise it’s no better than doofusort) On avg this also gives $O(N{\log }_2(N))$ Worst case it’ll just be doofus sort: $O(N^2)$

It’s better to choose the pivot at random so that bad actors cannot feed input that would make your algo as slow as doofusort

But the nice thing abt quicksort is that, if u make it right, you wont need an extra array unlike merge sort where you might need more memory for the temporary arrays.

We are parallelizing now amazing fantastic

Okay not really. but paco gave examples and asks “what is faster?”

1. Use doofusort and parallelize it on 1000 computers
2. Pacos laptop running merge sort. ans: paco’s laptop will win! b/c of complexity.