Check if array can be sorted with one swap

https://www.geeksforgeeks.org/check-if-array-can-be-sorted-with-one-swap/

Given an array containing N elements. Find if it is possible to sort it in non-decreasing order using atmost one swap.

Examples:

Input : arr[] = {1, 2, 3, 4}
Output : YES
The array is already sorted

Input : arr[] = {3, 2, 1}
Output : YES
Swap 3 and 1 to get [1, 2, 3]

Input : arr[] = {4, 1, 2, 3}
Output :NO

An efficient solution is to check in linear time. Let us consider different cases that may appear after one swap.

1. We swap adjacent elements. For example {1, 2, 3, 4, 5} becomes {1, 2, 4, 3, 5}
2. We swap non-adjacent elements. For example {1, 2, 3, 4, 5} becomes {1, 5, 3, 4, 2}

We traverse the given array. For every element, we check if it is smaller than previous element. We count such occurrences. If count of such occurrences is more than 2, then we cannot sort the array with one swap. If count is one, we can find elements to swap (smaller and its previous).
If count is two, we can find elements to swap (previous of first smaller and second smaller).
After swapping, we again check if array becomes sorted or not. We check this to handle cases like {4, 1, 2, 3}

int checkSorted(int n, int arr[])

{

    // Find counts and positions of 

    // elements that are out of order.

    int first = 0, second = 0;

    int count = 0;

    for (int i = 1; i < n; i++) {

        if (arr[i] < arr[i - 1]) {

            count++;

            if (first == 0)

                first = i;

            else

                second = i;

        }

    }

  

    // If there are more than two elements

    // are out of order.

    if (count > 2)

        return false;

  

    // If all elements are sorted already

    if (count == 0)

        return true;

  

    // Cases like {1, 5, 3, 4, 2}

    // We swap 5 and 2.

    if (count == 2)

        swap(arr[first - 1], arr[second]);

  

    // Cases like {1, 2, 4, 3, 5}

    else if (count == 1)

        swap(arr[first - 1], arr[first]);

  

    // Now check if array becomes sorted

    // for cases like {4, 1, 2, 3}

    for (int i = 1; i < n; i++)

        if (arr[i] < arr[i - 1])

            return false;

  

    return true;

}

A simple approach is to sort the array and compare the required position of the element and the current position of the element. If there are no mismatches, the array is already sorted. If there are exactly 2 mismatches, we can swap the terms that are not in position to get the sorted array.

bool checkSorted(int n, int arr[])
{
    // Create a sorted copy of original array
    int b[n];
    for (int i = 0; i < n; i++)
        b[i] = arr[i];
    sort(b, b + n);
 
    // Check if 0 or 1 swap required to
    // get the sorted array
    int ct = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] != b[i])
            ct++;
    if (ct == 0 || ct == 2)
        return true;
    else
        return false;
}

https://www.geeksforgeeks.org/sort-an-almost-sorted-array-where-only-two-elements-are-swapped/

Given an almost sorted array where only two elements are swapped, how to sort the array efficiently?

Examples :

Input:  arr[] = {10, 20, 60, 40, 50, 30}  
// 30 and 60 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}

Input:  arr[] = {10, 20, 40, 30, 50, 60}  
// 30 and 40 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}

Input:   arr[] = {1, 5, 3}
// 3 and 5 are swapped
Output:  arr[] = {1, 3, 5}

Expected time complexity is O(n) and only one swap operation to fix the array.

The idea is to traverse from rightmost side and find the first out of order element (element which is smaller than previous element). Once first element is found, find the other our of order element by traversing the array toward left side.

static void sortByOneSwap(int arr[], 

                          int n)

{

    // Travers the given array

    // from rightmost side

    for (int i = n - 1; i > 0; i--)

    {

        // Check if arr[i] 

        // is not in order

        if (arr[i] < arr[i - 1])

        {

            // Find the other element 

            // to be swapped with arr[i]

            int j = i - 1;

            while (j >= 0 && arr[i] < arr[j])

                j--;

  

            // Swap the pair

            int temp = arr[i];

            arr[i] = arr[j + 1];

            arr[j + 1] = temp;

      

            break;

        }

    }

}

https://www.geeksforgeeks.org/check-given-array-almost-sorted-elements-one-position-away/

Given an array with n distinct elements. An array is said to be almost sorted (non-decreasing) if any of its elements can occurs maximum of 1 distance away from their original places in sorted array. We need to find whether the given array is almost sorted or not.

    public static boolean almostSort(int A[], int n)

    {

        // One by one compare adjacents.

        for (int i = 0; i < n - 1; i++) {

            if (A[i] > A[i + 1]) {

                int temp = A[i];

                A[i] = A[i+1];

                A[i+1] = temp;

                i++;

            }

        }

       

        // check whether resultant is sorted or not

        for (int i = 0; i < n - 1; i++)

            if (A[i] > A[i + 1])

                return false;

       

        // is resultant is sorted return true

        return true;

    }