In this article, you will learn the insertion sort in python. To understand this program, you should have knowledge of the following Python Programming topics:
Insertion sort is a popular shorting 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 element from the unsorted list is inserted at the appropriate position in the sorted part. This process continues until the entire list is sorted. Basically, 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 at the sorted list therefore named Insertion sort.
Insertion Sort Program In Python
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]
Output: [17, 20, 26, 31, 44, 54, 55, 77, 93]
In the above function outer for loop is iterating over every element of the list from index 0 to the end of the list, the inner while loop swaps the values and inserts them to their appropriate positions this keeps on continuing until the entire list is sorted.