Algorithm and Data Structures in Python: Insertion Sort

Introduction

Same as bubble sort and selection sort, insertion sort is usually treated as one of the basic sorting algorithms, and similarly, it also utilized nest-loop, which means it has the same time complexity as bubble sort and selection sort.

Insertion Sort: How it Works?

Insertion sort starts from the left side of the array as it insert each element start from index 2 to the left side, which is a sorted portion of the array. Since it always keeps an the left part of the array sorted, It has a better performance than other sorting algorithms when dealing with situation that data keep coming continuously.

Implement Insertion Sort in Python

As shown in the code above, insertion sort loop through the array from the second element (index 1) while keeping the arr[i] as the currentValue, and while in the inner loop, it starts from the (i-1) element and iterated in a reversed order until it reaches the head of the array.

The trick in the inner loop is, whenever an element is found to be larger than the currentValue, it’s assigned to it’s next value, or in another word, arr[j] is sign to arr[j + 1]. And at the end of each outer loop, the currentValue is re-assigned to arr[j + 1]. That’s how the insertion is done, by duplicating one element to the right and assign the currentValue (Which is also the border of the sorted portion of this array) to the element that got duplicated.

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

4 Python Concepts That Beginners May Be Confused About

Canopy of trees in autumn

Migrating tasks and notes from Wunderlist to Joplin

Python HOW: Image processing for OCR using OpenCV

How to build your first Desktop Application in Python

A Little Cooler Death-and-Respawn Routine

EntityInPhp: quickly turning your MySQL tables into PHP objects

3-step tutorial to create BitUniverse Grid Trading Bot on Bitfinex exchange

Android MVVM Clean Architecture

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Yue

Yue

More from Medium

Hackerrank — Insert Node in linked list walkthrough #Python #Hackerrank

LeetCode Patterns Adventure 26 — Merge Two Binary Trees

LeetCode 15. 3Sum — Python Solution

Solving Array problems in O(n) time and O(1) space