Problem Link - Sort by swaps Practice Problem in Jump from 2* to 3*
Problem Statement:
You are given an array A of size n (not exceeding 500), you are allowed a maximum of n−1 swaps where in each swap you can choose any two indices i, j such that 0≤i, j≤n−1 and swap the values of A_i and A_j.
Approach:
Enumeration sort is a simple algorithm that sorts an array by finding the correct position for each element and placing it there. In this problem, we can modify it to count the swaps required and output the swap operations.
Steps to Solve the Problem:
-
Copy and Sort the Array: Create a copy of the original array and sort it using an in-built function to determine the target state of the array.
-
Swapping Process:
- Traverse the original array and for each element, check if it matches the element at the same index in the sorted array.
- If it doesn’t match, find the index
jin the original array that holds the correct element for the current indexi. - Swap the elements at indices
iandj. - Record the swap operation and increment the swap counter.
-
Stop After n−1 Swaps: Ensure the process stops after
n−1swaps, even if the array isn’t fully sorted, as the constraints limit the maximum number of swaps. -
Output: Print the number of swaps and the pairs of indices swapped.
Complexity:
- Time Complexity: O(n^2), as we may need to iterate through the array up to
n−1times to find and place elements. - Space Complexity:
O(n), due to storing the positions and the list of swaps.