tag:blogger.com,1999:blog-6314876008291942531.post9031348532001883545..comments2021-03-28T11:31:00.109-07:00Comments on Antonio Gulli's coding playground: Number of inversionsUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6314876008291942531.post-27711895231492392472012-01-13T14:46:34.256-08:002012-01-13T14:46:34.256-08:00Do an insertion sort, moving elements to the left,...Do an insertion sort, moving elements to the left, e.g.<br />Every time you move an element to the left, there _was_ an inversion.<br /><br />So: the number of inversions is the number of time you displaced the elements during insertion sort.Pascalhttps://www.blogger.com/profile/02506306462425421142noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-46559253540282400162010-06-10T11:34:22.911-07:002010-06-10T11:34:22.911-07:00I can think of an algorithm whose expected/average...I can think of an algorithm whose expected/average run time is O(n lg n). Idea is that of an augment tree data structure to hold the "right tree height" of a node at any point (assuming you are putting elements with values greater than itself to the right of the Node). Now, you simply start walking thru' the array and inserting elements into the tree. If you traverse to the left of the Node, increment the "inversion counter" by that Nodes' right tree height +1 (idea is all nodes to the right of the tree were *inserted* before the current node and are greater than this node). At the end of the insertion, the count will contain the inversion index. This runs in O(n log n) average case.Venkateshhttps://www.blogger.com/profile/15893132887136527161noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-65963731160656762802010-04-04T23:10:47.973-07:002010-04-04T23:10:47.973-07:00thanks made the correctionthanks made the correctioncodingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-34701439744643938552010-04-03T19:19:19.105-07:002010-04-03T19:19:19.105-07:00I think you got the question wrong. i A[j]. This a...I think you got the question wrong. i A[j]. This actually is an inversion isn't it?Anonymoushttps://www.blogger.com/profile/13377084356676401013noreply@blogger.com