In this lesson on python coding, we will talk about one of the Insertion Sort. This algorithm is a very common question for python coding interviews. This article will help if you are preparing for a python coding interview, so let's try to write a simple python program to implement the insertion sort in python.
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
To sort an array of size n in ascending order:
def insertion_sort(num_list): for num in range(1,len(num_list)): cur_val = num_list[num] pos = num while pos > 0 and num_list[pos-1] > cur_val : num_list[pos] = num_list[pos-1] pos = pos -1 num_list[pos]= cur_val return num_list print insertion_sort([54,26,93,17,77,31,44,55,20])
def insertion(s): for i in range(0,len(s)-1): if s[i]>s[i+1]: s[i],s[i+1]=s[i+1],s[i] for j in range(i,0,-1): if s[j]<s[j-1]: s[j],s[j-1]=s[j-1],s[j] print(s) insertion([5,2,1,9,0,4,6])
def insertionSort(alist): for i in range(1,len(alist)): #element to be compared current = alist[i] #comparing the current element with the sorted portion and swapping while i>0 and alist[i-1]>current: alist[i] = alist[i-1] i = i-1 alist[i] = current #print(alist) return alist print(insertionSort([5,2,1,9,0,4,6]))
All programs will print sorted array as output.