Sort an array in one swap whose two elements are swapped

Posted in

Sort an array in one swap whose two elements are swapped
vinaykhatri

Vinay Khatri
Last updated on March 5, 2024

    Problem Statement

    We have given an array in which all elements are sorted except two. Those two unsorted elements are swapped, and we need to swap them back so the array can be completely sorted. The challenge is we need to swap back the elements in linear time without duplicating the array or using any extra space.

    For Example

    Input: arr = [4, 7, 9, 18, 15, 16, 11, 20]
    
    Output arr= [4, 7, 9, 11, 15, 16, 18 , 20]

    Example

    In the above array arr , all the elements are sorted except 18 and 11 , we just need to swap these two elements, and we get a sorted array.

    Solution

    The solution to this problem statement is very simple, we just need to find out two index locations that conflict with the sorting flow of the array. We know that the complete array is sorted, and there are two elements in the array that are swapped.

    So, we can create a loop and compare adjacent elements and look for that if the previous element is greater than the current element. If yes, we will mark that index value with the pointer. The basic idea is to search for the index of two elements that conflict with the sorted array and then swap them.

    Algorithm

    1. Initialize two-pointers ptr1 and ptr2 that will store the index value of the first and second conflicting elements.
    2. Initialize a count variable that will flag the first and separate the first and second conflict elements.
    3. Initialize a variable prev indicating the previous element inside the loop, and initialize it with the first array element.
    4. Create a loop starting from the 1 index value up to the length of the array.
    5. Inside the loop, check if the previous element is greater than the current element.
    6. If the previous element is greater than the current element, set the previous value index number to pointer 1 ptr1 and the current value index number to pointer 2 ptr2 (in case if swapped elements are adjacent), and increase the count value by 1.
    7. In the else-if statement, check if the count value is 1, and set the index value of the current element to ptr2, representing the second conflicting element.
    8. At last, swap the elements, and we will get the sorted array.

    C++ Programming

    #include <iostream>
    using namespace std;
    
    // function to move zeros 
    //at the end of the array 
    void sort_swap(int arr[],int n)
    {
    	// represent the index value of two swapped elements
    	int ptr1=-1, ptr2=-1, temp;
    	//count for the 1st and 2nd conflicting elemetns
    	int count=0;
    		
    	//initial previous values
    	int prev = arr[0];
    	
    	//start the loop from 2nd element
    	for(int i=1; i<n; i++)
    	{
    		// check for conflict
            // if the current element is smaller
            // than previous element
    		if(arr[i]<prev)
    		{
    			if(count ==0)
    			{
    				//first conflict element
    				ptr1= i-1;
    				ptr2= i;   //if both the conflicting elements are adjacent
    				count++;
    			}
    			else if (count==1)
    			{	
    				// second conflict element
    				ptr2=i;
    			}
    		}
    		//update previous value
    		prev = arr[i];
    		
    		
    	}
            //swap the conflicted elements 
    	temp = arr[ptr1];
    	arr[ptr1] = arr[ptr2];
    	arr[ptr2] = temp;	
    
    }
     
    int main()
    {	//given array
    	int arr[]={4, 7, 9, 18, 15, 16, 11, 20};
    	
    	//length of the array
    	 int n = sizeof(arr) / sizeof(arr[0]);
    	 
    	sort_swap(arr, n);
    	for(int i=0; i<n;i++)
    	{
    		cout<<arr[i]<<" ";
    	}
        return 0;
    }
    

    Output

    4 7 9 11 15 16 18 20

    Python Programming

    # function to swap the elements to sort the array
    def sort_swap(arr, n):
        # represent the index value of two swapped elements
        ptr1= -1
        ptr2= -1
    
        # count for the 1st and 2nd conflicting elemetns
        count =0
    
        # initial previous values
        prev = arr[0]
    
        # start the loop from 2nd element
        for i in range(1, n):
            # value of the current element
            current = arr[i]
            # check for conflict
            # if the current element is smaller
            # than previous element
            if current < prev:
                # first conflict element
                if count ==0:
                    ptr1= i-1
                    ptr2=i    #if both the conflicting elements are adjacent
                    count+=1
                # second conflict element
                elif count==1:
                    ptr2 = i
            prev= arr[i]
    
        # swap the confilicted elemetns
        arr[ptr1], arr[ptr2] = arr[ptr2], arr[ptr1]
    
    if __name__=="__main__":
        #given array
        arr=[4, 7, 9, 18, 15, 16, 11, 20]
    
        #length of array
        n = len(arr)
    
    
        sort_swap(arr,n)
        print(arr)
    

    Output

    [4, 7, 9, 11, 15, 16, 18, 20]
    

    Complexity Analysis

    • Time Complexity: O(N) In the above program, we only use a single loop, which makes the algorithm complete in linear time complexity.
    • Space Complexity: The Space complexity of the above program is O(1) because we are not using any new array, and all the changes were made on the real array object.

    Wrapping Up!

    In this tutorial, we learned an algorithm to solve the problem "Sort an array in one swap whose two elements are swapped", and we also implemented the algorithm in C++ and Python programming languages. The problem statement is simple so does its solution. There are various ways to solve this problem, but we need to implement a solution with linear time complexity and constant space complexity.

    If you like this article or want to share a different approach to solve the above problem please feel free to comment down below.

    People are also reading:

    Leave a Comment on this Post

    0 Comments