Sort an array which contain 1 to n values

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
```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` ` `  `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] << ``" "``;     ` `} `

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] + ``" "``);  ` `    ``} ` `} ` ` `  `// This code is contributed by Manish Shaw  ` `// (manishshaw1) `

Python3

 `# Python3 program to sort an array of  ` `# numbers in range from 1 to n.  ` ` `  `# function for sort array  ` `def` `sortit(arr,n): ` `    ``for` `i ``in` `range``(n): ` `        ``arr[i] ``=` `i``+``1` ` `  `# Driver code ` `if` `__name__``=``=``'__main__'``: ` `    ``arr ``=` `[``10``, ``7``, ``9``, ``2``, ``8``, ``3``, ``5``, ``4``, ``6``, ``1` `] ` `    ``n ``=` `len``(arr) ` ` `  `    ``# for sort an array  ` `    ``sortit(arr,n) ` ` `  `    ``# for print all the element  ` `    ``# in sorted way  ` `    ``for` `i ``in` `range``(n): ` `        ``print``(arr[i],end``=``" "``) ` `  `  `# This code is contributed by  ` `# Shrikant13  `

C#

 `// Efficient C# program to sort an array of ` `// numbers in range from 1 to n. ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `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() ` `    ``{ ` `        ``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++)  ` `            ``Console.Write(arr[i] + ``" "``);  ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) `

PHP

 ` `

Output :

```1 2 3 4 5 6 7 8 9 10
```