In this article, you will learn about insertion sort in Python. To understand this program, you should know about the following Python Programming topics:
Insertion sort is a popular sorting algorithm, similar to selection sort. The unsorted list or array is divided into two parts, the left part being sorted, which is initially empty, and the right part being unsorted, which at the very beginning is the entire list.
At each iteration, an element from the unsorted list is inserted at the appropriate position in the sorted part. This process continues until the entire list is sorted. We are iterating over the element of the sorted list until the correct position is found. Since the items of the unsorted part are continuously inserted at appropriate positions in the sorted list, it is therefore named Insertion sort.
Insertion Sort Program In Python
def instertion_sort(seq):
for slice_end in range(len(seq)):
pos = slice_end
# inserting elements at correct position
while pos > 0 and seq[pos] < seq[pos - 1]:
(seq[pos], seq[pos - 1]) = (seq[pos - 1], seq[pos])
pos = pos - 1
# test input
l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
instertion_sort(l)
print(l)Output: [17, 20, 26, 31, 44, 54, 55, 77, 93]
In the above function, the outer for loop is iterating over every element of the list from index 0 to the end of the list, and the inner while loop swaps the values and inserts them to their appropriate positions This keeps on continuing until the entire list is sorted.
