Insertion sort examples in python - python coding

Insertion sort examples in python - python coding


Published at - Sep 09, 2021

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.

Introduction

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.

Time & Space complexity of insertion sort

Worst-case complexity: n^2
Average case complexity: n^2
Best case complexity: n
Space complexity: 1 

Algorithm

To sort an array of size n in ascending order:

  1. Iterate from arr[1] to arr[n] over the array.
  2. Compare the current element (key) to its predecessor.
  3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Some Facts about insertion sort 

  1. Simple implementation: Jon Bentley shows a three-line C version and a five-line optimized version
  2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms
  3. More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
  4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
  5. Stable; i.e., does not change the relative order of elements with equal keys
  6. In-place; i.e., only requires a constant amount O(1) of additional memory space Online; i.e., can sort a list as it receives it

Python example 1

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])

Python example 2

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])

 Python example 3

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.

I hope you like this article, to learn more articles like this you can click here. Thank you for reading.





About author

Harendra
Harendra Kanojiya

Hello, I am Harendra Kumar Kanojiya - Owner of this website and a Fullstack web developer. I have expertise in full-stack web development using Angular, PHP, Node JS, Python, Laravel, Codeigniter and, Other web technologies. I also love to write blogs on the latest web technology to keep me and others updated. Thank you for reading the articles.



Related Posts -

Follow Us

Follow us on facebook Click Here

Facebook QR
Scan from mobile
Join our telegram channel Click Here
Telegram QR
Scan from mobile