You are viewing a single comment's thread. Return to all comments →
I tried the same but i think its because quicksorting takes a lot of time to partition and then recounting them takes a lot of time
Well, I tried with merge sort. And merge sort takes like quicksort O(n log n) time. This is pretty fast. But anyway the timeout was not the problem. The problem is that it produces wrong answers. Has anyone an idea how this problem differs from the classic inversion count problem?
Ok, I think I got it: This problem is not about the number of inversions. It is about the minimum number of swaps.
You can try heapsort as it works beautifully in this case.