Merge sort's better than the usual, very obvious [Quadratic time O(n^2)] sorting methods like Insertion/Bubble/Selection methods, as it's rate of growth is logarithmic [O(nlogn)].
It follows the Divide and Conquer Paradigm
Source Code:
https://github.com/jaysonthomas/algorithms/blob/master/algs_course/week1/inversionCount.c
[I need to comment it. Plus, I'd like to write it in C++]
It follows the Divide and Conquer Paradigm
- DIVIDE into smaller sub-problems
- CONQUER each sub-problem via recursive calls
- COMBINE [clean-up work] solutions of sub-problems into one for the original problem.
Calculating the number of inversions
Motivation - to have a numerical similarity measure that quantifies how close two different ranked lists are to each other. Concept of Collaborative filtering is based on this eg: to make recommendations based on similar ratings people have given to the same products they bought which would indicate they might have the same tastes; hence you can make recommendations on products that one of them bought but the other hasn't and might like, because of the similar interests.
Motivation - to have a numerical similarity measure that quantifies how close two different ranked lists are to each other. Concept of Collaborative filtering is based on this eg: to make recommendations based on similar ratings people have given to the same products they bought which would indicate they might have the same tastes; hence you can make recommendations on products that one of them bought but the other hasn't and might like, because of the similar interests.
Source Code:
https://github.com/jaysonthomas/algorithms/blob/master/algs_course/week1/inversionCount.c
[I need to comment it. Plus, I'd like to write it in C++]
No comments:
Post a Comment