Sort an almost sorted array where only two elements are swapped - GeeksforGeeks

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

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.

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

            swap(arr[i], arr[j+1]);

            break;

        }

    }

}

Read full article from Sort an almost sorted array where only two elements are swapped - GeeksforGeeks