There are a lot of situation we need to sort. when we go to library, the book is also arrange in a sorted way to bring convenience to client to easily find them.
if a list of thing can be sort, so it must have a total order
Total order
image.png
In java, we should implement Comparable interface to make a class have a total order
Sort algorithm
the sort algorithm introduced in this class is basic. first is selection sort, in one for loop we fetch the min, and move it into beginning. then find next min.
insertion sort is a useful tool, when array is small and nearly sorted. please mock it like u find a new poker card, u need to find a suitable position to insert it.
shell sort
the idea of it is that move entries more than one position at a time by h-sorting the array
then they array will become nearly in order. then use insert sort will be super faster.
the tricky part is that which increment sequence to use?
image.png
image.png
the time complexity is also a interesting part of it. it is n ^ 3/2.
image.png
we usually use it for small subarrays
shuffling
one famous algorithm for it is knuth shuffle.
the way is that in iteration i, pick integer r between 0 and i uniformly at random.
then swap a[i] and a[r].
there are a very interesting example in the courses when a poker game website use wrong algorithm which lose money by hacker.
convex hull
image.png
convex hull application
image.png
image.png
the algorithm of graham scan to solve this problem have 3 step.
- choose point p with smallest y cooridinate
- sort points by polar angle with p
- consider points in order; discard unless it create a ccw turn
image.png
image.png
image.png
Quiz
Q1
image.png
this problem could be solved by the hash set, but this lecture is totally about elementary sort, we could use sort two array, then find a way to solve the problem.
think we can first sort by y then by x, and maintain two pointer. one iterate a[], one iterate b[].
move the small one, if they are same,then we find a answer.
Q2
image.png
the key idea behind it is to find a representative of a pattern. so we can sort both array, use the smallest alphabetic order as a representative to compare them are equal.
Q3
image.png
the idea behind it is more similar to the quick sort partition. we keep 3 pointer when is the boundary of 0 and 1, one is boundary of unknown and 1, one is boundary of unknown and 2.
so we move the middle pointer, to call color, know what the color of this unknown cell. then decide to swap to and last pointer(keep 2) or first pointer(keep 0).
extra credit
solve convex hull Jarvis Algorithm
this alogorithm we, need to find the upmost point. then for loop all other point find the max counter clock wise point to add it into the result
the time complexity if O (m * n), m is result data size, n is input data size.
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
网友评论