Hello Everyone,
You have given an array which contain 1 to n element, your task is to sort this array in an efficient way and without replace with 1 to n numbers.
Examples :
Input : arr[] = {10, 7, 9, 2, 8,
3, 5, 4, 6, 1};
Output : 1 2 3 4 5 6 7 8 9 10
Native approach :
Sort this array with the use of any type of sorting method. it takes O(nlogn) minimum time.
Efficient approach :
Replace every element with it’s position. it takes O(n) efficient time and give you the sorted array. Let’s understand this approach with the code below.
- C++
// Efficient C++ program to sort an array of
// numbers in range from 1 to n.
#include <bits/stdc++.h>
using namespace std;
// function for sort array
void sortit( int arr[], int n)
{
for ( int i = 0; i < n; i++) {
arr[i]=i+1;
}
}
// Driver code
int main()
{
int arr[] = { 10, 7, 9, 2, 8, 3, 5, 4, 6, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
// for sort an array
sortit(arr, n);
// for print all the element in sorted way
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
}
Output :
1 2 3 4 5 6 7 8 9 10
- JAVA
// Efficient Java program to sort an
// array of numbers in range from 1
// to n.
import java.io.*;
import java.util.*;
public class GFG {
// function for sort array
static void sortit( int []arr, int n)
{
for ( int i = 0 ; i < n; i++)
{
arr[i]=i+ 1 ;
}
}
// Driver code
public static void main(String args[])
{
int []arr = { 10 , 7 , 9 , 2 , 8 ,
3 , 5 , 4 , 6 , 1 };
int n = arr.length;
// for sort an array
sortit(arr, n);
// for print all the
// element in sorted way
for ( int i = 0 ; i < n; i++)
System.out.print(arr[i] + " " );
}
}
Output :
1 2 3 4 5 6 7 8 9 10