DEV Community

Cover image for Insertion sort algorithm
Aya Bouchiha
Aya Bouchiha

Posted on • Updated on

Insertion sort algorithm

Definition of insertion sort

Insertion sort is a type of sorting algorithms that works like the process of sorting playing cards, it divides the array into two parts, part of sorted numbers and other of unsorted numbers, the numbers that are in the wrong order ( numbers that exist in the unsorted part ) are inserted to the sorted part in the correct position.

Time and Space complexity of insertion sort

time Complexity Space Complexity
O(n2) O(1)

Algorithm explanation using an example

let's suppose we have an unsorted array [7,4,12,3],
the sorted part is 7 (bold styling), the unsorted part is from 4 to 3 (italic styling).

  1. (4 < 7) that's why we will insert 4 in the sorted part before 7 so the array will be [4,7,12,3]
  2. (12 > 7) therefore will keep it in the same position so the array will be [4,7,12,3]
  3. since 3 is smaller than 12,7 and 4, it will be in the first position, so the final array is [3,4,7,12]

Implementation of insertion sort algorithm using python

if you're not familiar with python, you can find the implementaion of insertion sort algorithm in other programming languages:

=> python:

def insertionSort(items: list) -> list:
    """
        [ name ]            => insertion sort
        [ type ]            => sorting algorithms
        [ time complexity ] => O(n^2)
        [ space complexity ]=> O(1)
        [ params ]          => (items) list to sort
        [ return ]          => sorted list
        [ code reference link ] => ("https://www.geeksforgeeks.org/insertion-sort/")       
    """
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and key < items[j] :
                items[j + 1] = items[j]
                j -= 1
        items[j + 1] = key
    return array
Enter fullscreen mode Exit fullscreen mode

References and useful resources

Special thanks to geeksforgeeks.
Have a good day :)
#day_9

Top comments (1)

Collapse
 
musman07 profile image
M-Usman07

cuitutorial.com/courses/data-struc...
n this tutorial, you will learn about insertion sort algorithm and its implementation in C, C++, Java and Python.

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.