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

Posted in  Vinay Khatri
Last updated on September 29, 2023

## 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;

//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);

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

# 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.