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.

A to -Z Java Script

How to pick a programming language/framework

How to create your Alexa skill using Blueprints?

Sharing Entity Between Client and Server with Dart

AIA Lifehack 2018

CS373 Spring 2022: Blake Chambers — Blog 8

AWS : Solutions Architect Associate Exam — Part 3

The Basics of Hash Table

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

Heaps, the python way

heap

Applicative order evaluation vs Normal order evaluation

Introduction to LinkedList