Interview Shuriken 52: Sort the Objects

Level EASY

You are given an array containing ‘n’ objects. On their creation, each object was given a creation number, which is a unique number from 1 to ‘n’. This means that an object with creation number ‘4’ was created just before the object with creation number ‘5’.

You have to sort the objects in-place on their creation number in O(n) and without any extra space. For simplicity, let’s assume you are given an integer array containing only the creation numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]

Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]

Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]

Output: [1, 2, 3, 4, 5, 6]

Input Format:

The first line of input contains an integer, that denotes the value of n. The following line contains n space separated integers, that denotes the creation numbers of n objects.

Constraints:

1 <= N <= 100000
1 <= A[i] <= N 
Time Limit: 0.5 seconds.

Output Format:

The first and only line of output contains sorted creation numbers.

Sample Input 1:

6
1 5 6 4 3 2

Sample Output 1:

1 2 3 4 5 6

	## Read input as specified in the question.
	## Print output as specified in the question.
	n=int(input())
	arr=sorted(list(map(int,input().split())))
	for i in range(len(arr)):
	print(arr[i],end=" ")

view raw Interview Shuriken 52: Sort the Objects.py hosted with ❤ by GitHub