Sort an almost sorted array where only two elements are swapped

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

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

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

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.

Below is C implementation of above idea.

Implementation:

void sortBySwap(int arr[], int n)
{
    // Traverse 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(arr[i], arr[j+1]);
            break;
        }
    }
}

The above program works in O(n) time and swaps only one element.

2 Thoughts on “Sort an almost sorted array where only two elements are swapped

  1. #include
    #include

    #define SIZE 6

    void swap(int *x,int *y)
    {
    int t;
    t=*x;
    *x=*y;
    *y=t;
    }

    void disp(int a[])
    {
    int i;
    printf(“\n”);
    for (i=0;i<SIZE;i++) printf("%d ", a[i]);
    }

    int main(void)
    {
    int a[SIZE]={2,16,8,10,4,18};
    int i=0;
    int pos_1=0,pos_2=0,flag=0;

    for (i=0;i a[i+1] && flag ==0 ) {flag=1;pos_1=i;continue;}
    else if (a[i] > a[i+1] && flag ==1) {pos_2=i+1;break;}
    }

    printf(“\n Pos = %d %d”,pos_1,pos_2);

    disp(a);
    swap(&a[pos_1],&a[pos_2]);
    disp(a);
    return 0;
    }

  2. Gaurav on March 2, 2016 at 1:01 pm said:

    public class SortAlmostSortedArray { public static void main(String[] args) { int[] arr = {1,2,3,9,5,6,7,8,4}; int instanceCount = 0 ; int notePositionFirstElement = 0 ; int notePositionSecElement = 0 ; for(int i = 0; i = 2) { break ; }else if(arr[i]>arr[i+1] && instanceCount==0) { notePositionFirstElement = i ; instanceCount = instanceCount + 1 ; }else if (arr[i]>arr[i+1] && instanceCount>0) { notePositionSecElement = i+1 ; instanceCount = instanceCount + 1 ; } } //swap notePositionFirstElement with notePositionSecElement int temp = arr[notePositionSecElement] ; arr[notePositionSecElement] = arr[notePositionFirstElement] ; arr[notePositionFirstElement] = temp ; } }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation