How to sort an array that contains 1 to n values in Python

Problem statement

You are given an array that contains 1 to n elements. Your task is to sort this array in an efficient way.

Example

Input:[8,6,9,4,3,7,2,6,1]

Expected output: [1,2,3,4,5,6,7,8,9]

Solution

We can solve this problem in two ways:

• Use the sort method.
• Use a for loop

The sort() method approach

• The sort() method will sort the original list on which it is applied.
• Time complexity = $O(nlog \space n)$

In the code snippet below:

• We initialize list lst with [8,6,9,4,3,7,2,6,1].
• We print the original list lst.
• We use the lst.sort() method to sort the original list.
• Finally, we print the sorted list lst.

The for loop approach

Now, we will try to use a for loop to solve this in $O(n)$ time complexity.

Approach

• Since the elements in the list are from 1 to n, we can fill the array one by one, like so:

  • arr[0] = 1, arr[1] = 2,… arr[n-1] = n

To sort the list in the code below:

• We use a for in range loop and go until n-1, where n is the length of the list, which can be calculated with len(lst).
• We replace every element at i with i+1.
• After the loop completes, the list lst is filled with sorted numbers.