Home » Data Structure » Array Data Structure

Sort 1 to N by swapping adjacent elements

C++ implementation to sort 1 to N by swapping adjacent elements.
Submitted by Vikneshwar GK, on January 25, 2022

Consider-an integer array, test1 of size n which has elements from 1 to n in any order, and another boolean array, test2 of size n-1, consisting of only 0 and 1. The constraint is test1[i] can be swapped with test1[i+1] only if test2[i] is 1, that is true. By following this, figure out whether the array test1 can be sorted or not.

Example:

Input:
test1[] = {2, 1, 5, 4, 3, 7, 6}
test2[] = {1, 0, 1, 1, 0, 1}

Output: Array can be sorted

Input:
test1[] = {5, 4, 1, 2, 3}
test2[] = {0, 0, 1, 0}

Output: Array cannot be sorted

Solution: Swapping elements for continuous 1's

This is a simple approach to check whether the array is sorted or not by following the given conditions. Here, the array is sorted for the positions where there are continuous 1s in the boolean array. After performing this operation, we will check whether the array is sorted or not by iterating through the array.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// Function to check array can be
// sorted or not
bool sortCheck(int array[], bool boolean[], int length)
{
    int i, j;

    // sort the positions where boolean
    // array has continuous 1s
    for (i = 0; i < length - 1; i++) {
        if (boolean[i]) {
            j = i;
            while (boolean[j])
                j++;

            // Sort the array from i to j
            sort(array + i, array + 1 + j);
            i = j;
        }
    }

    // Check if array is sorted or not
    for (i = 0; i < length; i++) {
        if (array[i] != i + 1)
            return false;
    }

    return true;
}

// main function
int main()
{
    int array[100], length;
    bool boolean[100];

    cout << "Enter Number of elements: ";
    cin >> length;

    for (int i = 0; i < length; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    cout << "Enter " << length - 1 << " boolean elements" << endl;
    for (int i = 0; i < length - 1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> boolean[i];
    }

    if (sortCheck(array, boolean, length)) {
        cout << "Array can be sorted";
    }
    else {
        cout << "Array cannot be sorted";
    }

    return 0;
}

Output:

Enter Number of elements: 7
Enter element 1:2
Enter element 2:1
Enter element 3:5
Enter element 4:4
Enter element 5:3
Enter element 6:7
Enter element 7:6
Enter 6 boolean elements
Enter element 1:1
Enter element 2:0
Enter element 3:1
Enter element 4:1
Enter element 5:0
Enter element 6:1
Array can be sorted

Time Complexity: O(n)