Minimum Swaps required to Sort
Given an array . Find the minimum number of swaps required to sort the array in non-decreasing order.
Example 1:
Input:
N = 5
arr = {1 5 4 3 2}
Output: 2
Explaination: swap 2 with 5 and 3 with 4.
Example 2:
Input:
N = 4
arr[] = {8 9 16 15}
Output: 1
Explaination: swap 16 and 15.
method 1:
int minSwaps(int a[], int n)
{ int temp[n]; int c=0; int k=0;
for(int i=0;i<n;i++)
temp[i]=a[i];
sort(temp,temp+n);
for(int i=0;i<n;i++)
{
if(a[i]!=temp[i])
{
c++;
for (int j = 0; j < n; j++)
{
if (a[j] == temp[i]) {
k=j;
break;
}
}
swap(a[i],a[k]);
}
}
return c ;
}
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
method 2:Expected Auxiliary Space: O(N)
int minSwaps(int a[], int n)
{ int c=0;
vector<pair<int,int>>v(n);
for(int i=0;i<n;i++)
v[i]=make_pair(a[i],i);
sort(v.begin(),v.end());
for(int i=0;i<n;i++)
{
if(v[i].second!=i)
{ c++;
swap(v[v[i].second],v[i]);
i--;
}
}
return c ;
}
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Expected Auxiliary Space: O(N)
No comments