You are given an array that contains 1 to n elements. Your task is to sort this array in an efficient way.
Input:[8,6,9,4,3,7,2,6,1]
Expected output: [1,2,3,4,5,6,7,8,9]
We can solve this problem in two ways:
sort
method.for
loopsort()
method approachsort()
method will sort the original list on which it is applied.In the code snippet below:
lst
with [8,6,9,4,3,7,2,6,1]
.lst
.lst.sort()
method to sort the original 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))
for
loop approachNow, we will try to use a for
loop to solve this in $O(n)$ time complexity.
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:
for in range
loop and go until n-1
, where n
is the length of the list, which can be calculated with len(lst)
.i
with i+1
.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
CONTRIBUTOR
View all Courses