Choose topic: extended merge sort
Algorithm: count inversions
count inversions - extended merge sort
1. http://jane4532.blogspot.ca/2013/06/zz-google-onsite-interview.html
2. http://www.geeksforgeeks.org/counting-inversions/
3. http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
4. https://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm
5. https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerI.pdf
6. http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf
problem statement:
In merge sort we do not swap all elements that are out of order with each other, we make larger distance "swaps".
Actionable Items:
Julia, write down favorite notes one sentence a time, on page 16, 17
Q. How to count inversions (a,b) with a ∈ A and b ∈ B?
A. Easy if A and B are sorted!
sort A sort B
3 7 10 14 18 2 11 16 17 23
binary search to count inversions (a, b) with a ∈ A and b ∈ B
3 7 10 14 18 2 11 16 17 23
5 2 1 1 0
-------
6. http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf
problem statement:
Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
Lecture Notes -
1. First lecture study:
1. How many inversions at most in the array n?
n(n-1)/2, special case, like {n, n-1, ..., 1}, any two nodes in the array is one inversion pair.
or: What is the maximum number of inversions for a list of length n?
n(n-1)/2
2. If each inversion is counted once, then the time of the algorithm is O(n^2), n is the number of elements in the array. Not optimal, we should not count each inversion.
3. Ideas to solve the algorithm:
Bubble sort?
Selection sort?
Insertion sort?
These are O(n^2)
Bubble and insertion sort count each individual inversion. To do better we must not count each individual inversion.
So, better algorithm is to beat O(n^2), using merge sort, nlogn - divide and conquer - sort and count inversion in the same time.
In merge sort we do not swap all elements that are out of order with each other, we make larger distance "swaps".
Questions: Sorting and counting inversion - merge part how to count the inversions.
Keywords in the lecture notes (7):
Collaborative filtering
inversions
Meta-search tools
Rank analysis
Recurrence Analysis - T(n) = 2 T(n/2) + cn
Rank analysis
Recurrence Analysis - T(n) = 2 T(n/2) + cn
similarity/ dissimilarity / in the middle
the number of out of place rankings
1. Merging part with diagram: <- Julia, can you draw a diagram as well
2. Count Inversions: Algorithm pseudo code - write down here:
2. 2nd Lecture Notes Study:
Julia, write down favorite notes one sentence a time, on page 16, 17
-------
Counting inversions: how to combine two subproblems?Q. How to count inversions (a,b) with a ∈ A and b ∈ B?
A. Easy if A and B are sorted!
Warmup algorithm.
Sort A and B.
For each element b ∈ B,
- binary search in A to find how elements in A are greater than b.
list A list B
7 10 18 3 14 17 23 2 11 16sort A sort B
3 7 10 14 18 2 11 16 17 23
binary search to count inversions (a, b) with a ∈ A and b ∈ B
3 7 10 14 18 2 11 16 17 23
5 2 1 1 0
-------
3. 3rd Lecture Notes Study: (Inversions Count)
http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
Great tips for sports coaching, https://t.co/6m29a8l1z0— jianmin chen (@jianminchen) July 22, 2016
Memorize 8 tips to help you to perform to your highest potential in Tennis (? code practice, etc.):
1. Let go of what others think
2. Perform for yourself, not to impress or to "not disappoint" others
3. Accept that you will make mistakes, and let them go
4. Focus on what you can control
5. Recognize when you are using negative self-talk and replace it with positive
6. Rather than performing perfectly, perform to see improvement
7. Be objective about your performance, not subjective
8. Focus on the Journey, not the Destination
Play not to lose or Play to win - Julia plays to win!
Some people play not to lose. I play to win each and every second I'm on court. #SpeedTakes aggression. pic.twitter.com/ae5xlriogs— Simona Halep (@Simona_Halep) July 2, 2016
Great post, the only one that explains the idea of counting the inversions, but it is still not clear to me.
ReplyDeleteIf Im sorting the items in the merge... then why we can supose that if Ai > Bi then the rest of the items in A are the needed inversions (the array is not sorted already! we are sorting it!) ?
Daniel, thank you to give out the encouraging words. I did review the algorithm, to answer your question, my answer is that we have to go through the merge sort as normal, but piggyback a task to count the inversions. So, go back to merge sort basics, merge part is the time to count the inversion, and then apply binary search to take advantage of sorting feature. Do not count the inversion one by one. Divide and conquer, we have to divide the array into two parts, continuously until there are only one for each section. Then, start to merge, and take care of counting inversions.
ReplyDeleteI like your post very much. It is very much useful for my research. I hope you to share more info about this. Keep posting ruby on rails online training hyderabad
ReplyDelete