Given an array arr[ ] of size N, The array is sorted except one element. position pos of misplaced element is given, the task is to make the complete array sorted by swapping any two elements any number of times.
Examples:
Input : N = 7, pos = 6, arr = {1, 2, 3, 4, 9, 15, 0}
Output: 0 1 2 3 4 9 15
Explanation:
Applying following swap arr can be sorted:1. swap element 0 and 1, Now arr is {0, 2, 3, 4, 9, 15, 1}
2. swap element 1 and 2, Now arr is {0, 1, 3, 4, 9, 15, 2}
3. swap element 2 and 3, Now arr is {0, 1, 2, 4, 9, 15, 3}
4. swap element 3 and 4, Now arr is {0, 1, 2, 3, 9, 15, 4}
5. swap element 4 and 9, Now arr is {0, 1, 2, 3, 4, 15, 9}
6. swap element 9 and 15, Now arr is {0, 1, 2, 3, 4, 9, 15}We can see now, the array arr[ ] has been sorted.
Input: N = 4, pos = 2, arr = {2, 3, 1, 4, }
Output: 1 2 3 4
Approach: This problem can be solved using greedy approach. Since the final array is to be sorted, elements on the left side of misplaced element must be smaller and elements on the right side must be greater. follow the steps given below to solve the problem:
- Traverse the array arr[ ], if element on left from pos arr[i], is greater than arr[pos], swap arr[i] and arr[pos].
- If element on right from pos arr[j], is smaller than arr[pos], swap arr[j] and arr[pos].
- Printing arr[ ] will be the last step.
Below is the implementation of the above approach.
C++
// C++ program for the above approach.#include <bits/stdc++.h>using namespace std;// Function to print sorted arrayvoid PrintSortedArr(int n, int pos, int arr[]){ // Traversing element of array. for (int i = 0; i < n; ++i) { // For the element on left of pos if (i < pos) { if (arr[pos] < arr[i]) { swap(arr[pos], arr[i]); } } // For the element on right of pos else if (i > pos) { if (arr[pos] > arr[i]) { swap(arr[pos], arr[i]); pos = i; } } } // Printing the sorted array cout << "Sorted Array: "; for (int i = 0; i < n; ++i) { cout << arr[i] << " "; }}// Driver Codeint main(){ // Given Input int N = 7, pos = 6; int arr[] = { 1, 2, 3, 4, 9, 15, 0 }; // Function Call PrintSortedArr(N, pos, arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to print sorted arraystatic void PrintSortedArr(int n, int pos, int arr[]){ // Traversing element of array. for (int i = 0; i < n; ++i) { // For the element on left of pos if (i < pos) { if (arr[pos] < arr[i]) { int t = arr[pos]; arr[pos] = arr[i]; arr[i] = t; } } // For the element on right of pos else if (i > pos) { if (arr[pos] > arr[i]) { int t = arr[pos]; arr[pos] = arr[i]; arr[i] = t; pos = i; } } } // Printing the sorted array System.out.print("Sorted Array: "); for (int i = 0; i < n; ++i) { System.out.print( arr[i] + " "); }}// Driver codepublic static void main(String args[]) { // Given Input int N = 7, pos = 6; int arr[] = { 1, 2, 3, 4, 9, 15, 0 }; // Function Call PrintSortedArr(N, pos, arr);}}// This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach.# Function to print sorted arraydef PrintSortedArr(n, pos, arr): # Traversing element of array. for i in range(n): # For the element on left of pos if (i < pos): if (arr[pos] < arr[i]): temp = arr[pos] arr[pos] = arr[i] arr[i] = temp # For the element on right of pos elif (i > pos): if (arr[pos] > arr[i]): temp = arr[pos] arr[pos] = arr[i] arr[i] = temp pos = i # Printing the sorted array print("Sorted Array: ",end="") for i in range(n): print(arr[i],end = " ")# Driver Codeif __name__ == '__main__': # Given Input N = 7 pos = 6 arr = [1, 2, 3, 4, 9, 15, 0] # Function Call PrintSortedArr(N, pos, arr) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{// Function to print sorted arraystatic void PrintSortedArr(int n, int pos, int []arr){ // Traversing element of array. for (int i = 0; i < n; ++i) { // For the element on left of pos if (i < pos) { if (arr[pos] < arr[i]) { int t = arr[pos]; arr[pos] = arr[i]; arr[i] = t; } } // For the element on right of pos else if (i > pos) { if (arr[pos] > arr[i]) { int t = arr[pos]; arr[pos] = arr[i]; arr[i] = t; pos = i; } } } // Printing the sorted array Console.Write("Sorted Array: "); for (int i = 0; i < n; ++i) { Console.Write( arr[i] + " "); }}// Driver codepublic static void Main(String []args) { // Given Input int N = 7, pos = 6; int []arr = { 1, 2, 3, 4, 9, 15, 0 }; // Function Call PrintSortedArr(N, pos, arr);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to print sorted array function PrintSortedArr(n, pos, arr) { // Traversing element of array. for (let i = 0; i < n; ++i) { // For the element on left of pos if (i < pos) { if (arr[pos] < arr[i]) { let temp = arr[pos]; arr[pos] = arr[i]; arr[i] = temp; } } // For the element on right of pos else if (i > pos) { if (arr[pos] > arr[i]) { let temp = arr[pos]; arr[pos] = arr[i]; arr[i] = temp; pos = i; } } } // Printing the sorted array document.write("Sorted Array: "); for (let i = 0; i < n; ++i) { document.write(arr[i] + " "); } } // Driver Code // Given Input let N = 7, pos = 6; let arr = [1, 2, 3, 4, 9, 15, 0]; // Function Call PrintSortedArr(N, pos, arr);// This code is contributed by Potta Lokesh </script> |
Sorted Array: 0 1 2 3 4 9 15
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
