We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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?
Lily's Homework
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.