//***********************************************************************//
//*******************Kth Selection - March 27th, 2017*******************//
//*********************************************************************//
-Another cloudy, grey, HB-less day...
-...and the TAs are (semi)frantically trying to figure out what we did before spring break
-ALSO: welcome back from spring break!
-NEVER MIND! HB just arrived
----------------------------------------
-One last "sort" we might as well go over: "Kth-Selection" (aka QUICK-SELECT)
-Let's say that we want to find the 5th smallest # in the array; to do this, we DON'T have to sort the whole array and then choose the 5th element
-Instead, kind of like Quick Sort, we choose a pivot, move all the larger/smaller items to the left/right, and then swap the pivot to its correct, FINAL position (EXACTLY like in quick-sort)
-This is known as the "prune-and-search" paradigm, btw
-We then CHECK the INDEX of the pivot
-If it is EQUAL to "k - 1," then we've found the kth smallest (since the pivot is in its final position, and we start counting from 0 (so 1st smallest # will be at position 0, etc.))
-If it is LESS than "k-1," we look in the right half of the list and start again
-If it is GREATER than "k-1," we look in the left half of the list and start again
e.g. suppose we're looking for the 1st smallest (k = 1):
-First, let's choose a pivot:
[33, 14, 7, |21|, 22, 40, 19]
-Now let's go through the quick-sort partitioning process
[21| 14, 7, 33, 22, 40, 19] -> [21| 14, 7, 19, 22, 40, 33]
-> [19, 14, 7, |21|, 22, 40, 33]
0 1 2 3 4 5 6
-Now, the pivot is in it's final position at index 3; 3 > (1-1 = 0), so let's look on the left side
[|19|, 14, 7] -> [7, 14, |19|]
0 1 2
-Pivot at 2, so let's continue on the left side
[14, |7|] -> [7, 14]
0 1
-7 is now at the 0 index, and 0 = k - 1, so, 7 is the 1st smallest #! We've found it!
-Another example (this time OUT-OF-PLACE, which requires us to change k):
-when k = 5
[62, 10, 47, 25, |18|, 81, 44, 49, 96]
-> [10, |18|, 47, 25, 62, 81, 44, 49, 96]
0 1 2 3 4 5 6 7 8
-Now, 1 < (5-1 = 4), so we're going to look in the right part of the array
-So, our new array we're looking at is:
[47, 25, 62, 81, 44, 49, 96]
0 1 2 3 4 5 6
-HOWEVER, since it's out of place, we now call "k-select" with a new K, so the "k = k - (pivotIndex + 1)" -> "5 - 2 = 3"
-Notice how the element at the 5th index in our old array (81) is the SAME one at the 3rd index in our new array; this is WHY we change K, because we can conclude that the 5th smallest element in the whole array is now only the 3rd smallest element in the new array
-So, if we continue through all these steps, we'll end up with the right answer!
-What's the efficiency of Kth-Selection / Quick-Select? Well, it has a best/average case performance of O(N)
-This is significantly faster than sorting; GREAT!
-However, it is based on Quicksort, so it has a worst-case runtime of O(n^2)
-T_T
-(...this only has like a (1/n)^n chance of happening though, so practically it's only a concern in the same way engineers kind of HAVE to worry about a hurricane striking Canada)
-So, on Wednesday we'll leave the wide, wide world of sorting for a brand-new topic: String Searching!
-Specifically, we'll look at brute-force searching, and then get to the exciting stuff: the Boyer-Moore Algorithm