|
This post is completed by 1 user
|
Add to List |
497. Minimum number of adjacent swaps to sort the given array
Given an array of integers, you are allowed to swap only adjacent elements in the array. write a program to find the minimum number of swaps to sort the given array.
Example:
Input[] : [2, 20, 15, 6, 10] Minimums adjacent swaps required sort the array: 5 Input[] : [10, 3, 4, 2, 5, 7, 9, 11] Minimums adjacent swaps required sort the array: 8
Approach:
This problem is very similar to find the number of reverse pairs in a given array. All these reverse pairs need to swap in order to sort the array, and that count will be the minimum number of adjacent swaps to sort the array. Let's take one example. 3, 1, 2. Reverse pairs are 2 [(3, 2) (3, 1)] and adjacent swaps required are 3 [ 3 with 1 and then swap 2 with 1). Why do these count matches? if you notice each swap with reducing one reverse pair, so x swaps will reduce reverse pairs. Like in our example- 3, 1, 2 after first swap 3 with 1. An array would be 1, 3, 2 and there is only one reverse pair which is (3, 2).
Time Complexity: O(nlogn)
Output:
Input[] : [10, 3, 4, 2, 5, 7, 9, 11] Minimums adjacent swaps required sort the array: 8