Tutorialspoint.dev

Sort 1 to N by swapping adjacent elements

Given an array A of size N consisting of elements 1 to 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 out if A can be sorted by swapping elements.

Examples:

Input : A[] = {1, 2, 5, 3, 4, 6}
        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[] = {2, 3, 1, 4, 5, 6}
        B[] = {0, 1, 1, 1, 1}
Output : A can not be sorted
We can not sort A by swapping elements.



Here we can swap only A[i] with A[i+1]. So to find whether array can be sorted or not. Using boolean array B we can sort array for a continuous sequence of 1 for B. At last we can check, if A is sorted or not.

C++

// CPP program to test whether array
// can be sorted by swapping adjacent
// elements using 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)
{
    int i, j;
  
    // Check bool array B and sorts
    // elements for continuos sequnce of 1
    for (i = 0; i < n - 1; i++) {
        if (B[i]) {
            j = i;
            while (B[j])
                j++;
  
            // Sort array A from i to j
            sort(A + i, A + 1 + j);
            i = j;
        }
    }
  
    // Check if array is sorted or not
    for (i = 0; i < n; i++) {
        if (A[i] != i + 1)
            return false;
    }
  
    return true;
}
  
// Driver program to test sortedAfterSwap()
int main()
{
    int A[] = { 1, 2, 5, 3, 4, 6 };
    bool B[] = { 0, 1, 1, 1, 0 };
    int n = sizeof(A) / sizeof(A[0]);
  
    if (sortedAfterSwap(A, B, n))
        cout << "A can be sorted ";
    else
        cout << "A can not be sorted ";
  
    return 0;
}

Java

import java.util.Arrays;
  
// Java program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
  
class GFG {
  
    // Return true if array can be
    // sorted otherwise false
    static boolean sortedAfterSwap(int A[],
                                   boolean B[], int n)
    {
        int i, j;
  
        // Check bool array B and sorts
        // elements for continuos sequnce of 1
        for (i = 0; i < n - 1; i++) {
            if (B[i]) {
                j = i;
                while (B[j]) {
                    j++;
                }
                // Sort array A from i to j
                Arrays.sort(A, i, 1 + j);
                i = j;
            }
        }
  
        // Check if array is sorted or not
        for (i = 0; i < n; i++) {
            if (A[i] != i + 1) {
                return false;
            }
        }
  
        return true;
    }
  
    // Driver program to test sortedAfterSwap()
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 5, 3, 4, 6 };
        boolean B[] = { false, true, true, true, false };
        int n = A.length;
  
        if (sortedAfterSwap(A, B, n)) {
            System.out.println("A can be sorted");
        }
        else {
            System.out.println("A can not be sorted");
        }
    }
}

Python3

# Python 3 program to test whether array
# can be sorted by swapping adjacent
# elements using boolean array
  
  
# Return true if array can be
# sorted otherwise false
def sortedAfterSwap(A, B, n) :
  
    # Check bool array B and sorts
    # elements for continuos sequnce of 1
    for i in range(0, n - 1) :
        if (B[i]== 1) :
            j = i
            while (B[j]== 1) :
                j = j + 1
   
            # Sort array A from i to j
            A = A[0:i] + sorted(A[i:j + 1]) + A[j + 1:]
            i = j
          
          
    # Check if array is sorted or not
    for i in range(0, n) :
        if (A[i] != i + 1) :
            return False
      
   
    return True
  
   
# Driver program to test sortedAfterSwap()
A = [ 1, 2, 5, 3, 4, 6 ]
B = [ 0, 1, 1, 1, 0 ]
n = len(A)
  
if (sortedAfterSwap(A, B, n)) :
    print("A can be sorted")
else :
    print("A can not be sorted")
      
  
# This code is contributed
# by Nikita Tiwari.

C#

// C# program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
using System;
class GFG {
  
    // Return true if array can be
    // sorted otherwise false
    static bool sortedAfterSwap(int[] A,
                                bool[] B,
                                int n)
    {
        int i, j;
  
        // Check bool array B and sorts
        // elements for continuos sequnce of 1
        for (i = 0; i < n - 1; i++) {
            if (B[i]) {
                j = i;
                while (B[j]) {
                    j++;
                }
                // Sort array A from i to j
                Array.Sort(A, i, 1 + j);
                i = j;
            }
        }
  
        // Check if array is sorted or not
        for (i = 0; i < n; i++) {
            if (A[i] != i + 1) {
                return false;
            }
        }
  
        return true;
    }
  
    // Driver Code
    public static void Main()
    {
        int[] A = { 1, 2, 5, 3, 4, 6 };
        bool[] B = { false, true, true, true, false };
        int n = A.Length;
  
        if (sortedAfterSwap(A, B, n)) {
            Console.WriteLine("A can be sorted");
        }
  
        else {
            Console.WriteLine("A can not be sorted");
        }
    }
}
  
// This code is contributed by Sam007

PHP

<?php
// PHP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
  
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap($A, $B, $n)
{
  
    // Check bool array B and sorts
    // elements for continuos sequnce of 1
    for ($i = 0; $i < $n - 1; $i++) 
    {
        if ($B[$i]) 
        {
            $j = $i;
            while ($B[$j])
                $j++;
  
            // Sort array A from i to j
            sort($A);
            $i = $j;
        }
    }
  
    // Check if array is sorted or not
    for ($i = 0; $i < $n; $i++)
    {
        if ($A[$i] != $i + 1)
            return false;
    }
  
    return true;
}
  
    // Driver Code
    $A = array(1, 2, 5, 3, 4, 6);
    $B = array(0, 1, 1, 1, 0);
    $n = count($A);
  
    if (sortedAfterSwap($A, $B, $n))
        echo "A can be sorted ";
    else
        echo "A can not be sorted ";
  
// This code is contributed by Sam007
?>

Output:

A can be sorted

Alternative Approach
Here we discuss a very intuitive approach which too gives the answer in O(n) time for all cases. The idea here is that whenever the binary array has 1, we check if that index in array A has i+1 or not. If it does not contain i+1, we simply swap a[i] with a[i+1].
The reason for this is that the array should have i+1 stored at index i. And if at all the array is sortable, then the only operation allowed is swapping. Hence, if the required 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.

C++

// CPP program to test whether array
// can be sorted by swapping adjacent
// elements using 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] != i + 1)
                swap(A[i], A[i + 1]);
        }
    }
  
    // Check if array is sorted or not
    for (int i = 0; i < n; i++) {
        if (A[i] != i + 1)
            return false;
    }
  
    return true;
}
  
// Driver program to test sortedAfterSwap()
int main()
{
    int A[] = { 1, 2, 5, 3, 4, 6 };
    bool B[] = { 0, 1, 1, 1, 0 };
    int n = sizeof(A) / sizeof(A[0]);
  
    if (sortedAfterSwap(A, B, n))
        cout << "A can be sorted ";
    else
        cout << "A can not be sorted ";
  
    return 0;
}
  

Java

// Java program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
class GFG
{
    // Return true if array can be
    // sorted otherwise false
    static int sortedAfterSwap(int[] A, 
                            int[] B, int n)
    {
        int t = 0;
        for (int i = 0; i < n - 1; i++) 
        {
            if (B[i] != 0
            {
                if (A[i] != i + 1)
                    t = A[i];
                    A[i] = A[i + 1];
                    A[i + 1] = t;
            }
        }
      
        // Check if array is sorted or not
        for (int i = 0; i < n; i++)
        {
            if (A[i] != i + 1)
                return 0;
        }
      
        return 1;
    }
      
    // Driver Code
    public static void main(String[] args)
    {
        int[] A = { 1, 2, 5, 3, 4, 6 };
        int[] B = { 0, 1, 1, 1, 0 };
        int n = A.length;
      
        if (sortedAfterSwap(A, B, n) == 0)
            System.out.println("A can be sorted");
        else
            System.out.println("A can not be sorted");
    }
}
  
// This code is contributed 
// by Mukul Singh.

Python3

# Python3 program to test whether array 
# can be sorted by swapping adjacent 
# elements using boolean array 
  
# Return true if array can be 
# sorted otherwise false 
def sortedAfterSwap(A,B,n):
    for i in range(0,n-1):
        if B[i]:
            if A[i]!=i+1:
                A[i], A[i+1] = A[i+1], A[i]
  
    # Check if array is sorted or not
    for i in range(n):
        if A[i]!=i+1:
            return False
    return True
  
# Driver program
if __name__=='__main__':
    A = [1, 2, 5, 3, 4, 6]
    B = [0, 1, 1, 1, 0]
    n =len(A)
    if (sortedAfterSwap(A, B, n)) :
        print("A can be sorted"
    else :
        print("A can not be sorted"
  
# This code is contributed by 
# Shrikant13

C#

// C# program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
using System;
  
class GFG
{
    // Return true if array can be
    // sorted otherwise false
    static int sortedAfterSwap(int[] A, 
                               int[] B, int n)
    {
        int t = 0;
        for (int i = 0; i < n - 1; i++) 
        {
            if (B[i] != 0) 
            {
                if (A[i] != i + 1)
                    t = A[i];
                    A[i] = A[i + 1];
                    A[i + 1] = t;
            }
        }
      
        // Check if array is sorted or not
        for (int i = 0; i < n; i++)
        {
            if (A[i] != i + 1)
                return 0;
        }
      
        return 1;
    }
      
    // Driver Code
    public static void Main()
    {
        int[] A = { 1, 2, 5, 3, 4, 6 };
        int[] B = { 0, 1, 1, 1, 0 };
        int n = A.Length;
      
        if (sortedAfterSwap(A, B, n) == 0)
            Console.WriteLine("A can be sorted");
        else
            Console.WriteLine("A can not be sorted");
    }
}
  
// This code is contributed 
// by Akanksha Rai

PHP

<?php 
// PHP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
  
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap(&$A, &$B, $n)
{
    for ($i = 0; $i < $n - 1; $i++) 
    {
        if ($B[$i]) 
        {
            if ($A[$i] != $i + 1)
            {
                $t = $A[$i];
                $A[$i] = $A[$i + 1];
                $A[$i + 1] = $t;
            }
        }
    }
  
    // Check if array is sorted or not
    for ($i = 0; $i < $n; $i++) 
    {
        if ($A[$i] != $i + 1)
            return false;
    }
  
    return true;
}
  
// Driver Code
$A = array( 1, 2, 5, 3, 4, 6 );
$B = array( 0, 1, 1, 1, 0 );
$n = sizeof($A);
  
if (sortedAfterSwap($A, $B, $n))
    echo "A can be sorted ";
else
    echo "A can not be sorted ";
  
// This code is contributed by ita_c
?>


Output:

A can be sorted


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter