Sort an array which contain 1 to n values

Software Development
#1

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