Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].
Example:
For N=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ? SOURCE: https://www.hackerearth.com/problem/approximate/swap-and-sort/
#include <iostream>
using namespace std;
void swaparr(int a[],int l,int r,int n) {
for(int i=l,j=r;i<=l+n&&j<=r+n;i++,j++)
swap(a[i],a[j]);
}
int findMax(int a[],int n) {
int index = 0;
for(int i=1;i<=n;i++)
if(a[i] > a[index])
index = i;
return index;
}
void sort(int a[],int n) {
for(int r=n-1;r>;0;r--) {
int index = findMax(a,r);
if(index != r) {
int l = min(r-index-1,index);
swaparr(a,index-l,r-l,l);
}
}
}
int main() {
int a[] = {7,23,8,234,3,6,41,334};
int n = 8;
sort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
Logic : find the max element in each operation and perform that swap such that maximum element goes to the end. Do this operation N times reducing array size each time by one and aiming to have max element in each operation. It doesn't necessary to have N swaps. It performs swaps only if the max element is not in its place. T = O(n2)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With