Insertion Sort Python Explained

Hi! Let’s do an Insertion Sort Example in Python, which will be fully explained 😊. We will be using Python 3.8.10. Let’s go!✨⚡

The Insertion Sort Algorithm takes each element of an unsorted list and, one at a time, uses comparison to insert each element into its proper place in a new, sorted list:

def insert_lst(lst,new):
  chk_loc = len(lst) - 1
  insrt_loc = 0
  while(chk_loc >= 0):
    if new > lst[chk_loc]:
        insrt_loc = chk_loc + 1
        chk_loc = - 1
    chk_loc = chk_loc - 1
  lst.insert(insrt_loc, new)
  return(lst)

def insertion_sort(lst):
  newlst = []
  while len(lst) > 0:
    new = lst.pop(0)
    newlst = insert_lst(newlst, new)
  return(newlst)

lst = [10,90,2,1,0,500,45,54,66,66]

sorted_lst = insertion_sort(lst)
print(sorted_lst)

#output
#[0, 1, 2, 10, 45, 54, 66, 66, 90, 500]

Let’s explain what is happening here:

1. We define the insert_lst function which will accept two parameters: lst and new.
   • Parameter lst is the unsorted initial list.
   • Parameter new is the new element to be inserted into the new, sorted list.
   • This function will accept these two parameters, loop through the list lst starting at the end of the list and comparing each element in the list to new to see if the new value is greater than that value.
   • If it meets this condition, new will be inserted at the location chk_loc+1 in the list.
   • If it doesn’t meet this condition, the new will compared to the next value and so on until the every member of lst is compared.
   • At the end, if new is not larger than any value in lst it is simply inserted at the beginning. If it is, it is inserted after the next smallest value in the list.
   • This function will be called once for every member of the initial sorted list.
2. The insert_lst function will return a sorted list of values in ascending order which includes the newly inserted value new.
3. We define the insertion_sort function that will take one parameter lst which is the unsorted list. It will remove the element at the first position of the initial list using the pop() method. This newly removed element will be passed as value new along with an empty newlst to the insert_lst function. As previously explained, this function will insert new at the proper position and return the sorted list to the calling function insertion_sort.
4. This function will call the insert_lst function once for every element of the initial unsorted list. The initial list will, at the same time, get shorter by one element with every iteration of the loop. When the unsorted list is empty, the sorted list is returned and the script terminates.

Easy right? If all goes well, you should see a list printed to the screen in ascending order! We can alter the program to sort the elements in descending order too if we wish:

def insert_lst(lst,new):
  chk_loc = len(lst) - 1
  insrt_loc = 0
  while(chk_loc >= 0):
    if new < lst[chk_loc]: #change sign to toggle ascending/descending order
        insrt_loc = chk_loc + 1
        chk_loc = - 1
    chk_loc = chk_loc - 1
  lst.insert(insrt_loc, new)
  return(lst)

def insertion_sort(lst):
  newlst = []
  while len(lst) > 0:
    new = lst.pop(0)
    newlst = insert_lst(newlst, new)
  return(newlst)


lst = [10,90,2,1,0,500,45,54,66,66]

sorted_lst = insertion_sort(lst)
print(sorted_lst)

#output
#[500, 90, 66, 66, 54, 45, 10, 2, 1, 0]

To change the sort order of our list, all we need to do is change the inequality sign at line 5 above. A very simple fix! When the code executes we will have a list is descending order.

Thanks for reading we hope this helped. Good luck! 👌👌👌