Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

communitycreator
python

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

Gutha Vamsi Krishna

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 n)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.
#initialize list
lst = [8,6,9,4,3,7,2,6,1]

#print original list
print("Original list  " + str(lst))

#sort the list
lst.sort()

#print the sorted list
print("Sorted list  " + str(lst))

The for loop approach

Now, we will try to use a for loop to solve this in O(n)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.
#initialize list
lst = [8,6,9,4,3,7,2,6,1]

#print original list
print("Original list  " + str(lst))

#sort the list
for i in range(len(lst)):
  lst[i] = i+1

#print the sorted list
print("Sorted list  " + str(lst))

RELATED TAGS

communitycreator
python
RELATED COURSES

View all Courses

Keep Exploring