Given an array arr[] consisting of first N natural numbers (N is even), the task is to find a sequence of swaps that can sort the array by swapping elements at positions X and Y if
N ≤ 2|X – Y|
Note: Consider 1-based indexing
Examples:
Input: N = 2, arr[] = { 2, 1 }
Output: 1 2
Explanation: Swapping elements at positions 1 and 2 sorts the array.Input: N = 4, arr[] = { 3, 4, 1, 2 }
Output:
1 3
2 4
Explanation:
Swap elements at positions 1 3. The array arr[] modifies to {1, 4, 3, 2}.
Swap elements at positions 2 4. The array arr[] modifies to {1, 2, 3, 4}.
Approach: The idea to solve this problem is to use an array position[] to maintain the positions of elements in array arr[] and perform swaps of arr[x] an arr[y] as well as position[arr[x]] and position[arr[y]]. Follow the steps below to solve the problem:
- Initialize an array newArr[] to refer to elements directly by position.
- Initialize a vector position to store the positions of the original array elements and vector answer to store the swaps performed.
- Traverse from i=1 to N and check the conditions below:
- If position[i] = i : Continue to the next integer as this one is already at its right position.
- If |position[i] – i| >= N/2 : Call perform_swap(i, position[i])
- Otherwise: Keep variable initial_position to maintain the current position of integer i i.e. position[i]
- If |position[i]-1| >= N/2 : Call perform_swap(position[i], 1)
- If |i-1| >= N/2 : Call perform_swap(i, 1) and perform_swap(initial_position, 1)
- Otherwise: Call perform_swap(1, N), perform_swap(N, i) and perform_swap(1, initial_position).
- Otherwise: Call perform_swap(position[i], N) and perform_swap(N, i);
- If |position[i]-1| >= N/2 : Call perform_swap(position[i], 1)
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <algorithm>#include <iostream>#include <vector>using namespace std;// Function to swap values in arr and positionvoid perform_swap(vector<int>& arr, vector<int>& position, vector<pair<int, int> >& answer, int x, int y){ // Swap position[arr[x]] and position[arr[y]] swap(position[arr[x]], position[arr[y]]); // Swap arr[x] and arr[y] swap(arr[x], arr[y]); // Push x and y to the answer vector answer.push_back({ x, y });}// Function to find the sequence of swaps// that can sort the arrayvoid sortBySwap(int N, int arr[]){ // Shifted vector of Array arr vector<int> newArr(N + 1, 0); for (int i = 0; i < N; i++) newArr[i + 1] = arr[i]; // Keep an vector to maintain positions vector<int> position(N + 1, 0); // Vector to maintain the swaps performed vector<pair<int, int> > answer; // Assign position of elements in position array for (int i = 1; i <= N; i++) position[newArr[i]] = i; // Traverse from 1 to N for (int i = 1; i <= N; i++) { // If element is already at it's right position if (i == position[i]) continue; // If current and right place can be directly // swapped if (abs(i - position[i]) >= N / 2) { perform_swap(newArr, position, answer, i, position[i]); } else { // Initial position of integer i int initial_position = position[i]; // If |position[i]-1| >= N/2 : // Call perform_swap(position[i], 1) if (abs(position[i] - 1) >= N / 2) { perform_swap(newArr, position, answer, position[i], 1); // If |i-1| >= N/2 : Call perform_swap(i, 1) // and perform_swap(initial_position, 1) if (abs(i - 1) >= N / 2) { perform_swap(newArr, position, answer, i, 1); perform_swap(newArr, position, answer, initial_position, 1); } // Otherwise: Call perform_swap(1, N), // perform_swap(N, i) and // perform_swap(1, initial_position). else { perform_swap(newArr, position, answer, 1, N); perform_swap(newArr, position, answer, N, i); perform_swap(newArr, position, answer, 1, initial_position); } } // Otherwise: Call perform_swap(position[i], N) // and perform_swap(N, i); else { perform_swap(newArr, position, answer, position[i], N); perform_swap(newArr, position, answer, N, i); } } } // Print the sequences which sorts // the given array for (int i = 0; i < (int)answer.size(); i++) printf("%d %d\n", answer[i].first, answer[i].second);}// Driver Codeint main(){ // Input Array int arr[] = { 3, 4, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call sortBySwap(N, arr);} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; }}class GFG{static void swap(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp;}// Function to swap values in arr and positionstatic void perform_swap(int[] arr, int[] position, List<Pair> answer, int x, int y){ // Swap position[arr[x]] and position[arr[y]] swap(position, arr[x], arr[y]); // Swap arr[x] and arr[y] swap(arr, x, y); // Push x and y to the answer vector answer.add(new Pair(x, y));}// Function to find the sequence of swaps// that can sort the arraystatic void sortBySwap(int N, int arr[]){ // Shifted vector of Array arr int[] newArr = new int[N + 1]; for(int i = 0; i < N; i++) newArr[i + 1] = arr[i]; // Keep an vector to maintain positions int[] position = new int[N + 1]; // Vector to maintain the swaps performed @SuppressWarnings("unchecked") List<Pair> answer = new ArrayList(); // Assign position of elements in position array for(int i = 1; i <= N; i++) position[newArr[i]] = i; // Traverse from 1 to N for(int i = 1; i <= N; i++) { // If element is already at it's // right position if (i == position[i]) continue; // If current and right place can // be directly swapped if (Math.abs(i - position[i]) >= N / 2) { perform_swap(newArr, position, answer, i, position[i]); } else { // Initial position of integer i int initial_position = position[i]; // If |position[i]-1| >= N/2 : // Call perform_swap(position[i], 1) if (Math.abs(position[i] - 1) >= N / 2) { perform_swap(newArr, position, answer, position[i], 1); // If |i-1| >= N/2 : Call // perform_swap(i, 1) and // perform_swap(initial_position, 1) if (Math.abs(i - 1) >= N / 2) { perform_swap(newArr, position, answer, i, 1); perform_swap(newArr, position, answer, initial_position, 1); } // Otherwise: Call perform_swap(1, N), // perform_swap(N, i) and // perform_swap(1, initial_position). else { perform_swap(newArr, position, answer, 1, N); perform_swap(newArr, position, answer, N, i); perform_swap(newArr, position, answer, 1, initial_position); } } // Otherwise: Call perform_swap(position[i], // N) and perform_swap(N, i); else { perform_swap(newArr, position, answer, position[i], N); perform_swap(newArr, position, answer, N, i); } } } // Print the sequences which sorts // the given array for(int i = 0; i < answer.size(); i++) System.out.println(answer.get(i).first + " " + answer.get(i).second);}// Driver codepublic static void main(String[] args){ // Input Array int arr[] = { 3, 4, 1, 2 }; int N = arr.length; // Function Call sortBySwap(N, arr);}}// This code is contributed by jithin |
Python3
# Python3 program for the above approach# Function to swap values in arr and positiondef perform_swap(x, y): global arr, position, answer # Swap position[arr[x]] and position[arr[y]] position[arr[x - 1]], position[arr[y - 1]] = position[arr[y - 1]], position[arr[x - 1]] arr[x - 1], arr[y - 1] = arr[y - 1], arr[x - 1] # Push x and y to the answer vector answer.append([x, y])# Function to find the sequence of swaps# that can sort the arraydef sortBySwap(N, arr): global newArr, position, answer for i in range(N): newArr[i + 1] = arr[i] # Assign position of elements in position array for i in range(1, N + 1): position[newArr[i]] = i # Traverse from 1 to N for i in range(N + 1): # If element is already at it's right position if (i == position[i]): continue # If current and right place can be directly # swapped if (abs(i - position[i]) >= N // 2): perform_swap(i, position[i]) else: # Initial position of integer i initial_position = position[i] # If |position[i]-1| >= N/2 : # Call perform_swap(position[i], 1) if (abs(position[i] - 1) >= N // 2): perform_swap(position[i], 1) # If |i-1| >= N/2 : Call perform_swap(i, 1) # and perform_swap(initial_position, 1) if (abs(i - 1) >= N // 2): perform_swap(i, 1) perform_swap(initial_position, 1) # Otherwise: Call perform_swap(1, N), # perform_swap(N, i) and # perform_swap(1, initial_position). else: perform_swap(1, N) perform_swap(N, i) perform_swap(1, initial_position) # Otherwise: Call perform_swap(position[i], N) # and perform_swap(N, i) else: perform_swap(position[i], N) perform_swap(N, i) # Print the sequences which sorts # the given array for i in answer: print(i[0], i[1])# Driver Codeif __name__ == '__main__': # Input Array arr = [3, 4, 1, 2] N = len(arr) newArr = [0 for i in range(N+1)] position = [i for i in range(N+1)] answer = [] # Function Call sortBySwap(N, arr)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class Pair { public int first, second; public Pair(int first, int second) { this.first = first; this.second = second; }}public class GFG{ static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } // Function to swap values in arr and position static void perform_swap(int[] arr, int[] position, List<Pair> answer, int x, int y) { // Swap position[arr[x]] and position[arr[y]] swap(position, arr[x], arr[y]); // Swap arr[x] and arr[y] swap(arr, x, y); // Push x and y to the answer vector answer.Add(new Pair(x, y)); } // Function to find the sequence of swaps // that can sort the array static void sortBySwap(int N, int[] arr) { // Shifted vector of Array arr int[] newArr = new int[N + 1]; for(int i = 0; i < N; i++) newArr[i + 1] = arr[i]; // Keep an vector to maintain positions int[] position = new int[N + 1]; // Vector to maintain the swaps performed List<Pair> answer = new List<Pair>(); // Assign position of elements in position array for(int i = 1; i <= N; i++) position[newArr[i]] = i; // Traverse from 1 to N for(int i = 1; i <= N; i++) { // If element is already at it's // right position if (i == position[i]) continue; // If current and right place can // be directly swapped if (Math.Abs(i - position[i]) >= N / 2) { perform_swap(newArr, position, answer, i, position[i]); } else { // Initial position of integer i int initial_position = position[i]; // If |position[i]-1| >= N/2 : // Call perform_swap(position[i], 1) if (Math.Abs(position[i] - 1) >= N / 2) { perform_swap(newArr, position, answer, position[i], 1); // If |i-1| >= N/2 : Call // perform_swap(i, 1) and // perform_swap(initial_position, 1) if (Math.Abs(i - 1) >= N / 2) { perform_swap(newArr, position, answer, i, 1); perform_swap(newArr, position, answer, initial_position, 1); } // Otherwise: Call perform_swap(1, N), // perform_swap(N, i) and // perform_swap(1, initial_position). else { perform_swap(newArr, position, answer, 1, N); perform_swap(newArr, position, answer, N, i); perform_swap(newArr, position, answer, 1, initial_position); } } // Otherwise: Call perform_swap(position[i], // N) and perform_swap(N, i); else { perform_swap(newArr, position, answer, position[i], N); perform_swap(newArr, position, answer, N, i); } } } // Print the sequences which sorts // the given array for(int i = 0; i < answer.Count; i++) Console.WriteLine(answer[i].first + " " + answer[i].second); } // Driver code static public void Main () { // Input Array int[] arr = { 3, 4, 1, 2 }; int N = arr.Length; // Function Call sortBySwap(N, arr); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// Javascript program for the above approachclass Pair{ constructor(first, second) { this.first = first; this.second = second; }}function swap(a, i, j){ let temp = a[i]; a[i] = a[j]; a[j] = temp;}// Function to swap values in arr and positionfunction perform_swap(arr, position, answer, x, y){ // Swap position[arr[x]] and position[arr[y]] swap(position, arr[x], arr[y]); // Swap arr[x] and arr[y] swap(arr, x, y); // Push x and y to the answer vector answer.push(new Pair(x, y));}// Function to find the sequence of swaps// that can sort the arrayfunction sortBySwap(N, arr){ // Shifted vector of Array arr let newArr = new Array(N + 1); for(let i = 0; i < N; i++) newArr[i + 1] = arr[i]; // Keep an vector to maintain positions let position = new Array(N + 1); // Vector to maintain the swaps performed let answer = []; // Assign position of elements // in position array for(let i = 1; i <= N; i++) position[newArr[i]] = i; // Traverse from 1 to N for(let i = 1; i <= N; i++) { // If element is already at it's // right position if (i == position[i]) continue; // If current and right place can // be directly swapped if (Math.abs(i - position[i]) >= N / 2) { perform_swap(newArr, position, answer, i, position[i]); } else { // Initial position of integer i let initial_position = position[i]; // If |position[i]-1| >= N/2 : // Call perform_swap(position[i], 1) if (Math.abs(position[i] - 1) >= N / 2) { perform_swap(newArr, position, answer, position[i], 1); // If |i-1| >= N/2 : Call // perform_swap(i, 1) and // perform_swap(initial_position, 1) if (Math.abs(i - 1) >= N / 2) { perform_swap(newArr, position, answer, i, 1); perform_swap(newArr, position, answer, initial_position, 1); } // Otherwise: Call perform_swap(1, N), // perform_swap(N, i) and // perform_swap(1, initial_position). else { perform_swap(newArr, position, answer, 1, N); perform_swap(newArr, position, answer, N, i); perform_swap(newArr, position, answer, 1, initial_position); } } // Otherwise: Call perform_swap(position[i], // N) and perform_swap(N, i); else { perform_swap(newArr, position, answer, position[i], N); perform_swap(newArr, position, answer, N, i); } } } // Print the sequences which sorts // the given array for(let i = 0; i < answer.length; i++) document.write(answer[i].first + " " + answer[i].second + "<br>");}// Driver code// Input Arraylet arr = [ 3, 4, 1, 2 ];let N = arr.length;// Function CallsortBySwap(N, arr);// This code is contributed by unknown2108</script> |
Output:
1 3 2 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
