Sort an almost sorted array where only two elements are swapped

Posted in

Sort an almost sorted array where only two elements are swapped
vinaykhatri

Vinay Khatri
Last updated on October 6, 2024

    Problem

    How can an almost-sorted array with only two members swapped be effectively sorted?

    Sample Input

    [1, 5, 3]

    Sample Output

    [1, 3, 5]

    Explanation

    3 and 5 got swapped

    Approach

    The goal is to go from right to left and discover the first out-of-order number (a number that is smaller than the previous number). Once the first number is located, traverse the array toward the left side to find the other out-of-order element. The approach takes O(N) time.

    C++ Programming

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //function to sort an array
    void sortArray(int arr[], int n)
    {
        // Traverse the given array from right side
        for (int i = n-1; i > 0; i--)
        {
            // if arr[i] is not in order
            if (arr[i] < arr[i-1])
            {
                int j = i-1;
                while (j>=0 && arr[i] < arr[j])
                    j--;
                swap(arr[i], arr[j+1]);
                break;
            }
        }
    }
    int main()
    {
        int arr[] = {1, 5, 3};
        int n = sizeof(arr)/sizeof(arr[0]);
    
    
        sortArray(arr, n);
    
        for(int i=0;i<n;i++) cout<<arr[i]<<" ";
        return 0;
    }
    

    Output

    1 3 5

    C Programming

    #include<stdio.h>
    
    //function to sort an array
    void sortArray(int arr[], int n)
    {
        // Traverse the given array from right side
        for (int i = n-1; i > 0; i--)
        {
            // if arr[i] is not in order
            if (arr[i] < arr[i-1])
            {
                int j = i-1;
                while (j>=0 && arr[i] < arr[j])
                    j--;
                int temp = arr[i];  //swap the elements
                arr[i] = arr[j+1];
                arr[j+1] = temp;
                break;
            }
        }
    }
    void main()
    {
        int arr[] = {1, 5, 3};
        int n = sizeof(arr)/sizeof(arr[0]);
    
        sortArray(arr, n);
        for(int i=0;i<n;i++) printf("%d ",arr[i]);
    }

    Output

    1 3 5

    Java Programming

    import java.io.*;
    
    class Solution
    {
    //function to sort 
    static void sortArray(int arr[], int n)
    {
       // Traverse the given array
       // from right side
       for (int i = n - 1; i > 0; i--)
       {
         // 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 
          int temp = arr[i];
          arr[i] = arr[j + 1];
          arr[j + 1] = temp;
         
          break;
         }
       }
    }
    
    public static void main(String[] args)
    {
       int arr[] = {1, 5, 3};
       int n = arr.length;
       
       sortArray(arr, n);
    
       for (int i = 0; i < n; i++)
          System.out.print(arr[i] + " ");
        System.out.println();
    }
    }

    Output

    1 3 5

    People are also reading:

    Leave a Comment on this Post

    0 Comments