Given an array p[] of size N representing a permutation of first N natural numbers, where N is an even number, the task is to sort the array by taking a pair of indices a, b and swap p[a] and p[b] in each operation, where 2 * |a – b| ? N. Print the pairs of indices swapped in each operation.
Examples:
Input: p[] = {2, 5, 3, 1, 4, 6}
Output: 3
1 5
2 5
1 4
Explanation:
Operation 1: Swap p[1] and p[5]. Therefore, p[] modifies to {4, 5, 3, 1, 2, 6}.
Operation 2: Swap p[2] and p[5]. Therefore, p[] modifies to {4, 2, 3, 1, 5, 6}.
Operation 3: Swap p[1] and p[4]. Therefore, p[] modifies to {1, 2, 3, 4, 5, 6}.
Therefore, the array is sorted.Input: p[] = {1, 2, 3, 4}
Output: 0
Approach: Follow the steps below to solve the problem:
- Create an array, posOfCurrNum[] that stores the position of the numbers present in p[].
- Iterate in the range [1, N] using the variable i and set posOfCurrNum[p[i]] to i.
- Declare a vector of pair ans to store the swaps that are to be performed to sort the given array p[].
- Iterate in the range [1, N] using the variable i
- If p[i] equal to i, then that means the current number i is already present at the right position. So, continue to the next iteration.
- Initialize a variable j with posOfCurrNum[i] to store the current position of the number i.
- Now, arises 4 cases:
- Case 1: If |i – j| * 2 is greater than n, then, swap(i, j) and store this pair in ans.
- Case 2: if n/2 is less than or equal to i – 1, then, swap(i, 1) ? swap(1, j) ? swap(i, 1) and store these pair in ans.
- Case 3: if n/2 is less than or equal to n – j, then, swap(i, n) ? swap(j, n) ? swap(i, n) and store these pair in ans.
- Case 4: if n/2 is less than j -1 and n/2 is less than or equal to n – i, then swap(i, n) ? swap(n, 1) ? swap(1, j) ? swap(1, n) ? swap(i, n) and store these pair in ans.
- Print the size of the vector, ans.
- Traverse the vector of pairs, ans, and print each pair.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to swap integers// in an operationvoid Swap(int x, int y, int p[], int posOfCurrNum[]){ swap(posOfCurrNum[p[x]], posOfCurrNum[p[y]]); swap(p[x], p[y]);}// Function to sort permutation// using given operationsvoid sortArray(int p[], int n){ // Store the position of the // array elements int posOfCurrNum[n + 1]; for (int i = 1; i <= n; i++) { posOfCurrNum[p[i]] = i; } // Store the result vector<pair<int, int> > ans; // Traverse the given array, p[] for (int i = 1; i <= n; i++) { // If current number is already // present at the right position if (p[i] == i) { continue; } // Store the current position of // the number 'i' int j = posOfCurrNum[i]; // Case 1: If both the indices // satisfies the given condition if (abs(i - j) * 2 >= n) { Swap(i, j, p, posOfCurrNum); ans.push_back({ i, j }); } // Case 2: If the current number // 'i' is present at right side // of half of the given array else if (n / 2 <= i - 1) { Swap(1, i, p, posOfCurrNum); ans.push_back({ i, 1 }); Swap(1, j, p, posOfCurrNum); ans.push_back({ 1, j }); Swap(i, 1, p, posOfCurrNum); ans.push_back({ i, 1 }); } // Case 3: If the position of the // current number 'i' is left side // of half of the given array else if (n - j >= n / 2) { Swap(i, n, p, posOfCurrNum); ans.push_back({ i, n }); Swap(j, n, p, posOfCurrNum); ans.push_back({ j, n }); Swap(i, n, p, posOfCurrNum); ans.push_back({ i, n }); } // Case 4: For all other cases else { Swap(i, n, p, posOfCurrNum); ans.push_back({ i, n }); Swap(n, 1, p, posOfCurrNum); ans.push_back({ n, 1 }); Swap(1, j, p, posOfCurrNum); ans.push_back({ 1, j }); Swap(1, n, p, posOfCurrNum); ans.push_back({ 1, n }); Swap(i, n, p, posOfCurrNum); ans.push_back({ i, n }); } } // Print the number of operations cout << ans.size() << '\n'; // Print the steps for (auto p : ans) cout << p.first << " " << p.second << '\n';}// Driver Codeint main(){ // Given Input int n = 6; // Append 0 to consider // 1-based indexing int p[] = { 0, 2, 5, 3, 1, 4, 6 }; // Function Call sortArray(p, n); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class pair{ int first, second; pair(int first, int second) { this.first = first; this.second = second; }}class GFG { // Function to swap integers // in an operation static void Swap(int x, int y, int p[], int posOfCurrNum[]) { int t1 = posOfCurrNum[p[x]]; posOfCurrNum[p[x]] = posOfCurrNum[p[y]]; posOfCurrNum[p[y]] = t1; int t2 = p[x]; p[x] = p[y]; p[y] = t2; } // Function to sort permutation // using given operations static void sortArray(int p[], int n) { // Store the position of the // array elements int[] posOfCurrNum = new int[n + 1]; for (int i = 1; i <= n; i++) { posOfCurrNum[p[i]] = i; } // Store the result ArrayList<pair > ans=new ArrayList<>(); // Traverse the given array, p[] for (int i = 1; i <= n; i++) { // If current number is already // present at the right position if (p[i] == i) { continue; } // Store the current position of // the number 'i' int j = posOfCurrNum[i]; // Case 1: If both the indices // satisfies the given condition if (Math.abs(i - j) * 2 >= n) { Swap(i, j, p, posOfCurrNum); ans.add(new pair( i, j )); } // Case 2: If the current number // 'i' is present at right side // of half of the given array else if (n / 2 <= i - 1) { Swap(1, i, p, posOfCurrNum); ans.add(new pair( i, 1 )); Swap(1, j, p, posOfCurrNum); ans.add(new pair( 1, j )); Swap(i, 1, p, posOfCurrNum); ans.add(new pair( i, 1 )); } // Case 3: If the position of the // current number 'i' is left side // of half of the given array else if (n - j >= n / 2) { Swap(i, n, p, posOfCurrNum); ans.add(new pair( i, n )); Swap(j, n, p, posOfCurrNum); ans.add(new pair( j, n )); Swap(i, n, p, posOfCurrNum); ans.add(new pair( i, n )); } // Case 4: For all other cases else { Swap(i, n, p, posOfCurrNum); ans.add(new pair( i, n )); Swap(n, 1, p, posOfCurrNum); ans.add(new pair( n, 1 )); Swap(1, j, p, posOfCurrNum); ans.add(new pair( 1, j )); Swap(1, n, p, posOfCurrNum); ans.add(new pair( 1, n )); Swap(i, n, p, posOfCurrNum); ans.add(new pair( i, n )); } } // Print the number of operations System.out.println(ans.size()); // Print the steps for (pair pp : ans) System.out.println(pp.first+" "+pp.second); } // Driver code public static void main(String[] args) { // Given Input int n = 6; // Append 0 to consider // 1-based indexing int p[] = { 0, 2, 5, 3, 1, 4, 6 }; // Function Call sortArray(p, n); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to swap integers# in an operationdef Swap(x, y, p, posOfCurrNum): posOfCurrNum[p[x]], posOfCurrNum[p[y]] = posOfCurrNum[p[y]], posOfCurrNum[p[x]] p[x], p[y] = p[y], p[x] return p, posOfCurrNum# Function to sort permutation# using given operationsdef sortArray(p, n): # Store the position of the # array elements posOfCurrNum = [0] * (n + 1) for i in range(1, n + 1): posOfCurrNum[p[i]] = i # Store the result ans = [] # Traverse the given array, p[] for i in range(1, n + 1): # If current number is already # present at the right position if (p[i] == i): continue # Store the current position of # the number 'i' j = posOfCurrNum[i] # Case 1: If both the indices # satisfies the given condition if (abs(i - j) * 2 >= n): p, posOfCurrNum = Swap(i, j, p, posOfCurrNum) ans.append([i, j]) # Case 2: If the current number # 'i' is present at right side # of half of the given array elif (n // 2 <= i - 1): p, posOfCurrNum = Swap(1, i, p, posOfCurrNum) ans.append([i, 1]) p, posOfCurrNum = Swap(1, j, p, posOfCurrNum) ans.append([1, j]) p, posOfCurrNum = Swap(i, 1, p, posOfCurrNum) ans.append([i, 1]) # Case 3: If the position of the # current number 'i' is left side # of half of the given array elif (n - j >= n // 2): p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) p, posOfCurrNum = Swap(j, n, p, posOfCurrNum) ans.append([j, n]) p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) # Case 4: For all other cases else: p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) p, posOfCurrNum = Swap(n, 1, p, posOfCurrNum) ans.append([n, 1]) p, posOfCurrNum = Swap(1, j, p, posOfCurrNum) ans.append([1, j]) p, posOfCurrNum = Swap(1, n, p, posOfCurrNum) ans.append([1, n]) p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) # Print the number of operations print(len(ans)) # Print the steps for p in ans: print(p[0], p[1])# Driver Codeif __name__ == '__main__': # Given Input n = 6 # Append 0 to consider # 1-based indexing p = [ 0, 2, 5, 3, 1, 4, 6 ] # Function Call sortArray(p, n)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to swap integers // in an operation static void Swap(int x, int y, int[] p, int[] posOfCurrNum) { int t1 = posOfCurrNum[p[x]]; posOfCurrNum[p[x]] = posOfCurrNum[p[y]]; posOfCurrNum[p[y]] = t1; int t2 = p[x]; p[x] = p[y]; p[y] = t2; } // Function to sort permutation // using given operations static void sortArray(int[] p, int n) { // Store the position of the // array elements int[] posOfCurrNum = new int[n + 1]; for (int i = 1; i <= n; i++) { posOfCurrNum[p[i]] = i; } // Store the result List<Tuple<int,int>> ans = new List<Tuple<int,int>>(); // Traverse the given array, p[] for (int i = 1; i <= n; i++) { // If current number is already // present at the right position if (p[i] == i) { continue; } // Store the current position of // the number 'i' int j = posOfCurrNum[i]; // Case 1: If both the indices // satisfies the given condition if (Math.Abs(i - j) * 2 >= n) { Swap(i, j, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, j)); } // Case 2: If the current number // 'i' is present at right side // of half of the given array else if (n / 2 <= i - 1) { Swap(1, i, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, 1)); Swap(1, j, p, posOfCurrNum); ans.Add(new Tuple<int,int>(1, j)); Swap(i, 1, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, 1)); } // Case 3: If the position of the // current number 'i' is left side // of half of the given array else if (n - j >= n / 2) { Swap(i, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, n)); Swap(j, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(j, n)); Swap(i, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, n)); } // Case 4: For all other cases else { Swap(i, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, n)); Swap(n, 1, p, posOfCurrNum); ans.Add(new Tuple<int,int>(n, 1)); Swap(1, j, p, posOfCurrNum); ans.Add(new Tuple<int,int>(1, 4)); Swap(1, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(1, 6)); Swap(i, n, p, posOfCurrNum); ans.Add(new Tuple<int,int>(i, n)); } } // Print the number of operations Console.WriteLine(ans.Count); // Print the steps foreach(Tuple<int,int> pp in ans) Console.WriteLine(pp.Item1+" "+pp.Item2); } // Driver code static void Main() { // Given Input int n = 6; // Append 0 to consider // 1-based indexing int[] p = { 0, 2, 5, 3, 1, 4, 6 }; // Function Call sortArray(p, n); }}// This code is contributed by mukesh07. |
Javascript
<script>// Javascript program for the above approach// Function to swap integers// in an operationfunction Swap(x, y, p, posOfCurrNum){ let temp = posOfCurrNum[p[x]]; posOfCurrNum[p[x]] = posOfCurrNum[p[y]]; posOfCurrNum[p[y]] = temp; temp = p[x]; p[x] = p[y]; p[y] = temp;}// Function to sort permutation// using given operationsfunction sortArray(p, n){ // Store the position of the // array elements let posOfCurrNum = new Array(n + 1); for (let i = 1; i <= n; i++) { posOfCurrNum[p[i]] = i; } // Store the result let ans = []; // Traverse the given array, p[] for (let i = 1; i <= n; i++) { // If current number is already // present at the right position if (p[i] == i) { continue; } // Store the current position of // the number 'i' let j = posOfCurrNum[i]; // Case 1: If both the indices // satisfies the given condition if (Math.abs(i - j) * 2 >= n) { Swap(i, j, p, posOfCurrNum); ans.push([ i, j ]); } // Case 2: If the current number // 'i' is present at right side // of half of the given array else if (n / 2 <= i - 1) { Swap(1, i, p, posOfCurrNum); ans.push([ i, 1 ]); Swap(1, j, p, posOfCurrNum); ans.push([ 1, j ]); Swap(i, 1, p, posOfCurrNum); ans.push([ i, 1 ]); } // Case 3: If the position of the // current number 'i' is left side // of half of the given array else if (n - j >= n / 2) { Swap(i, n, p, posOfCurrNum); ans.push([ i, n ]); Swap(j, n, p, posOfCurrNum); ans.push([ j, n ]); Swap(i, n, p, posOfCurrNum); ans.push([ i, n ]); } // Case 4: For all other cases else { Swap(i, n, p, posOfCurrNum); ans.push([ i, n ]); Swap(n, 1, p, posOfCurrNum); ans.push([ n, 1 ]); Swap(1, j, p, posOfCurrNum); ans.push([ 1, j ]); Swap(1, n, p, posOfCurrNum); ans.push([ 1, n ]); Swap(i, n, p, posOfCurrNum); ans.push([ i, n ]); } } // Print the number of operations document.write(ans.length + '<br>'); // Print the steps for (let p of ans) document.write(p[0] + " " + p[1] + '<br>');}// Driver Code // Given Input let n = 6; // Append 0 to consider // 1-based indexing let p = [ 0, 2, 5, 3, 1, 4, 6 ]; // Function Call sortArray(p, n); // This code is contributed by gfgking.</script> |
Output:
9 1 4 2 6 6 1 1 4 1 6 2 6 4 1 1 5 4 1
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
