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

Initialize twopointers
ptr1
andptr2
that will store the index value of the first and second conflicting elements. 
Initialize a
count
variable that will flag the first and separate the first and second conflict elements. 
Initialize a variable
prev
indicating the previous element inside the loop, and initialize it with the first array element.  Create a loop starting from the 1 index value up to the length of the array.
 Inside the loop, check if the previous element is greater than the current element.

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 2ptr2
(in case if swapped elements are adjacent), and increase the count value by 1. 
In the elseif statement, check if the
count
value is 1, and set the index value of the current element toptr2,
representing the second conflicting element.  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= i1; 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= i1 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
Leave a Comment on this Post