Princeton Alogorithm COS226 Week

In java source code implementation, Arrays.sort and Collections.sort for primitive type and object use different sort algorithm.
for objects java will use merge sort, because it is stable sort.
for primitive type, jave use quick sort, because stable is useless on primitive type.

why stable is useful in object. Because sometimes we need first sort by a column then sort by b column. so when a are same, b have order on it. if a sort algorithm is not stable it can not achieve this result.

basic plan of merge sort is

1. divide array into two halves.
2. recursively sort each half
3. merge two halves

image.png

merge sort performance

image.png

merge sort time complexity is O (n lg n), memory is O (n)

merge sort improvement

1. merge sort has too much overhead for tiny subarrays, cutoff to insertion sort for ~ 15 item
2. stop if already sorted. is the biggest item in first half <= smallest item in second half. it helps for partially-ordered arrays

3. eliminate the copy to the auxiliary array. it could save time. this is a very tricky one, in merge side, we need swap aux and arr roles.

   
   image.png

bottom up merge sort

image.png

compare-based lower bound for sorting

below is a decision tree, we can know the height of the tree is lower bound because it list all possibility.

image.png
image.png

merge sort is optimal with respect to number compares
but it is not optimal with respect to space usage

some situation lower bound may not hold

image.png

Comparator and Polar order

in java, if u want to sort, u can implement comparable interface on this class. u also can pass a comparator to achieve it. it support more flexibility. for example as a point class, sometimes u want to sort by x, sometimes u want to sort by y. one class only can have one compareTo method , but we can use comparator to achieve it.

image.png
image.png

stability

image.png

insertion sort and merge sort are stable. selection and shell short are not

QUIZ

Q1

image.png

we only keep the origin array first half to the aux array, then we maintain two point to do the merge on the origin array. note that the first half is equivalent to the empty. so in the extreme case, all the last half move to the first half. we still have aux array to copy to the last half.

Q2

image.png

we can calculate counting inversions on merge sort template. it is also divide and conquer; there are two half, we calculate left part inversions number, also calculating the right part inversions. then we need to merge them, in this process, we only need to calculate the part from right side go ahead left side.
for example. left side {1,3, 5} right side {2,4} so 2 is smaller than 3,5. so when merge to {1,2,?, ?, ?} it will add two more inversion. 4 is smaller than 5. so when merge to {1,2,3,4,?}, it will add one more inversion.

Q3

image.png
this question is hard. and the answer in https://stackoverflow.com/questions/12167630/algorithm-for-shuffling-a-linked-list-in-n-log-n-time is totally wrong.
u can use this algorithm, tester will failed.
above algorithm's problem is uneven probability.
why?
because they choose left part and right part with 0.5 and 0.5, and ignore the size of each part.
take an easy example, left is only 1, right have 2, 3
so 1 move to the first is 0.5, move to the second is 0.25, move to the third is 0.25

so the correct way should calculate current two list size. so same example. only 33.333% to move 1, 66.6% to move 2. if 2 go to the front.then we have 50 % and 50 % to choose 1 and 3.
now the 1 have 33% chance to go to first, 66% * 50% go the the second, and 66% * 50 % go to the last.
some people may ask how about 2, it have 66% chance to go the first.
u should keep the previous step when only have 2 and 3. 2 have 50% chance become previous than 3, so same as 3.
in another try, may situtaiton is 1 and 3,2. with 50% probability. so it is uniform.

Project Colinear Points

Colinear point is a good project for u to see the difference for the good algorithm and brute force alogorihm.

image.png

first thing need to take care, is when client pass the parameter in our class, best practice is to copy them. and when we return our data structure to client, better is also to clone it.
it is for program safety. because we pass the reference to the heap. client get the reference then can do change on the heap. it will break the our class view.

the second hard part is how to avoid sub line in the answer. there are 5 points in a line. if u do not deal with dedup, u will output 1,2,3,4,5 . then 2,3,4,5
but what program expect is only 1,2,3,4,5
after sort by point slope, we can maintain a field, is there has smaller point, when we calculate 2, we found there is a 1 with same slope, 1 is smaller than 2, so we could know, 2,3,4,5 is already in the 1's answer set.

so the total solution is like below:
step 1. sort point to check duplicate
step 2. for each point, we sort based on the slope order, then same slope will become neighbor.
step 3. check if there is continuous slope are same and count larger than 4. and there is no same slope point which is smaller than current one.
step 4. add the answer when satisfy above condition

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226