Given an array A of size N. A boolean array B consisting of N-1 elements indicates that if B[i] is 1 then A[i] can be swapped with A[i+1]. Find if A can be sorted by swapping elements.
Examples:
Input : A[] = {1, 6, 52, 31, 47, 60}
B[] = {0, 1, 1, 1, 0}
Output : A can be sorted
We can swap a[3] with a[4] and then a[4] with a[5].
Input : A[] = {27, 32, 16, 42, 58, 66}
B[] = {0, 1, 1, 1, 1}
Output : A can not be sorted
We can not sort A by swapping elements.
RECOMMENDED: Characteristics or features of an Algorithm
Approach:
The idea here is that whenever the binary array has 1, we check in array A, if A[i]>A[i+1] or not.
If this condition is true, we simply swap A[i] with A[i+1]. The reason for this is that the array needs to be sorted.
Hence if the sorted condition is not satisfied, we simply swap.
If the array is sortable, swapping will take us one step closer to the correct answer.
And as expected, if the array is not sortable, then swapping would lead to just another unsorted version of the same array.
Implementation in C++:
// CPP program to test whether array
// can be sorted by swapping adjacent
// elements using a boolean array
#include <bits/stdc++.h>
using namespace std;
// Return true if array can be
// sorted, otherwise false
bool sortedAfterSwap(int A[], bool B[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if(B[i])
{
if(A[i] > A[i + 1])
swap(A[i], A[i + 1]);
}
}
// Check if array is sorted or not
for (int i = 1; i < n; i++) {
if (A[i] < A[i - 1])
return false;
}
return true;
}
// Driver program to test sortedAfterSwap()
int main()
{
int A[] = {1, 6, 52, 31, 47, 60};
bool B[] = {0, 1, 1, 1, 0};
int n = sizeof(A) / sizeof(A[0]);
if (sortedAfterSwap(A, B, n))
cout << "A can be sorted\n";
else
cout << "A cannot be sorted\n";
return 0;
}
Output:
A can be sorted
Time Complexity: O(n)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.