//************************************************************************//
//*********Advanced Sorting Algorithms (cont.) - March 15th, 2017********//
//**********************************************************************//
-Da-dum, da-dum, da-dee, da DON'T FORGET TO FILL OUT HOUSING dum, da-dee, da-dee, da-ree-ree-ree-ree, da-dum, da-dum, da-dum-dum-dum-dum
---------------------------------------
-So, we gave you guys a quick overview of the concepts behind "Quick sort;" let's go into more detail
-"So, it's a sort, and it's quick - ta-da?"
-You have an array, and you choose a random element in the array as the PIVOT
-You THEN move all of the elements less than the pivot to the LEFT, and all of the elements GREATER than the pivot to the RIGHT
-Notice that the pivot itself will be in its final, sorted position after the swap...kind of like selection sort
-So, you're hoping that the pivot is close to the median of the elements, so that the left/right branches are the same length
-More algorithmically...
0) Randomly choose an element in the array as the pivot
[34, 7, 4, 25, 6, 19, 12, |15|, 3, 81]
*
1) SWAP the pivot with the element at [0] (DON'T bother doing a comparison)
[15|, 7, 4, 25, 6, 19, 12, 34, 3, 81]
2) Then, we make a pointer "i" at [1] and a pointer [j] at (array.length-1)
[15|, 7, 4, 25, 6, 19, 12, 34, 3, 81]
i j
3) We then move "i" towards the end of the array UNTIL we hit an element GREATER than the pivot (we CAN move past the end of the array, since then we're guaranteed to have passed j) (we do NOT stop if the element is equal to the pivot)
-When this happens, we similarly move j towards the front of the array UNTIL we hit an element SMALLER than the pivot (or the front of the array, i.e. the pivot itself)
[15|, 7, 4, 25, 6, 19, 12, 34, 3, 81]
i j
-THEN, we SWAP "i" and "j" in the array (UNLESS index "j" is < "i", implying i/j passed each other)
[15|, 7, 4, 3, 6, 19, 12, 34, 25, 81]
i j
-...AND add +1 to i and -1 to (i++ and j--), to avoid having to do a redundant comparison
[15|, 7, 4, 3, 6, 19, 12, 34, 25, 81]
i j
4) We continue this process until index "i" is GREATER than "j" (i.e., they cross!)
[15, 7, 4, 3, 6, 12, 19, 34, 25, 81]
j i
-Once this happens, we know everything from [1] to [j] is LESS than the pivot, and everything from [i] to [length-1] is GREATER than the pivot
5) So, we then swap the pivot with "j", so that all the elements LEFT of the pivot are less than it, and all elements to the RIGHT of it are greater
[12, 7, 4, 3, 6, |15|, 19, 34, 25, 81]
6) Then, repeat the algorithm on BOTH of the left/right branches!
7) Repeat until we reach the BASE CASE: an array length of either 0 or 1
-even on an array of length 2, the algorithm still works; it looks stupid, but it DOES work
-In the case of an array length of 2, i and j will start pointing at the same element, then either i will move outside of the array, causing them to cross, or j will move to the pivot, causing them to cross
e.g.
[34, |81|]
[81|, 34]
i,j
[81|, 34]
j i
[34, 81]
-This implementation is NOT stable (its swaps can change the order of duplicates), but it is also IN-PLACE
-So, for your homework, DON'T create a new array when you're splitting branches!
-A FEW EDGE CASES:
-if the index of "j" EQUALS [0] (the index of the pivot), you don't need to do anything
-...probably some other stuff
-Again, this sort has an AVERAGE runtime of O(nlog(n)), but if we choose a bad pivot each time (i.e. the max/min of the list), then Quick sort becomes a glorified selection sort with a worst-case runtime of O(n^2)
-RADIX SORT is very...odd. It ONLY works with INTEGERS.
45, 32, 37, 87, 103
-So, intuitively, we look at this list and know that 103 is largest, because it has 3 digits, right? And we know 87 is larger than 37 because 8 is in the tens place and is greater than 3, right?
-The way that radix sort works is like this...kind of
-We make a bunch of "buckets" (implementation-wise, usually queues) with numbers assigned to them
[] [] [] [] ...
0 1 2 3
-there are TWO main versions of radix-sort: least signficant digit (where we start with, whaddya know, the least significant digit), and most-significant digit
-annnnnnnd...that probably didn't make much sense. Don't worry; we'll go over this again on Friday.