Sort an array in one swap whose two elements are swapped

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:

• Rearrange an array such that arr[i] = i
• WAP to Count no. of alphabets, digits and spaces present in a file
• Minimum Edit Distance
• Majority Element
• The Stock Span Problem
• Check for pairs in an array with a particular sum
• Find maximum of minimum for every window size in a given array
• WAP to Print Square Using * Character
• WAP to Print Triangle Using * Character
• Count all Possible Paths from Top Left to Bottom Right in a Matrix