Table of Contents
show
- In-place comparison-based sorting algorithm.
- A sub-list is maintained which is always sorted
- For example, the lower part of an array is maintained to be sorted
- An element which is to be inserted in this sorted sub-list has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort
Program
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
#Get the elements from user
n = int(input("Enter the number of elements:"))
A=[]
print("Enter the elements:")
for i in range(n):
A.append(int(input()))
insertionSort(A)
print("Sorted Array:")
for i in range(n):
print("At index",i,"the element is:",A[i])Output
Enter the number of elements: 4
Enter the elements:
21
-1
3
4
Sorted Array:
At index 0 the element is: -1
At index 1 the element is: 3
At index 2 the element is: 4
At index 3 the element is: 21Example
Views: 0