Princeton Alogorithm COS226 Week
this lecture we introduce the sort algorithm which used in java primitive type. quick sort.
The basic plan is
- shuffle the array
- partition so that, for some j (no larger entry to the left of j, no small entry to the right of j. a[j] is dividing line.
-
then sort each piece recursively
image.png
image.png
performance
image.png
the best case is n lg n, the worst case 1/2 *n ^ 2, the average case 1.39 n lg n
the random shuffle is important, it have probabilistic guarantee against worst case. and it is the basis for math model that can be validated with experiments
quick sort is an in-place sorting algorithm.
depth of recursion is logarithmic extra space (with high probability)
improvement
-
even quick sort has too much overhead for tiny subarrays. so we can insertion sort when small subarrays
-
best choic of pivot item is median. so we can use median of 3 random items
selection
given an array of N items, find kth smallest item.
image.png
quick selet takes linear time on average.
duplicate keys
above quick sort to solve data with a lot of duplicate is not efficient.
but is better than put all items equal to the partitioning item on one side.
so to avoid the time complexity degradation, we should use 3-way quick sort
image.png
image.png
system sort
image.png
larger array we could use tukey's ninther to improve.
it use the median of the median of 3 samples, each of 3 entries.
approximates the median of 9
uses at most 12 compares.
image.png
a killer inut for java system sort
image.png
below there are a lot of choice for sort algorithms. which one should we use?
image.png
Yaroslavskiy sort now is used in java 7+, which is Dual pivot quick sort
image.png
QUIZ
Q1
image.png
choose one nut to partition the bolts, and then use matched bolt to partition the nuts. then we have two sub array to solve. then the steps is same as quick sort.
Q2
image.png
all three problem could be solved by the third one.
to solve third one, i will introduce a concept cut. if cut is -1, so we will cut the array into two part. the first part last element index is -1, the second part first element index is 0.
so we can binary search the cut on the small length array. according to cut1 and k, we should know where is cut2
we cut the two array. so there are four element is neighbor of the two cut.
L1 is the first array left part last element, R1 is the first aray right part first element.
the invariant is cut1 + 1 + cut2 + 2 == k
if the place we cut which R1 < L2, means cut1 could be larger
if R2 < L1, means cut1 too larger, should be less.
if L2 < R1 && L1 < R2. we find the correct cut, so just return ans.
Q3
image.png
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
