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

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:

• javascript
• c++
• c#
• java
• php

=> 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

References and useful resources

• https://www.geeksforgeeks.org/insertion-sort/
• https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm
• https://www.youtube.com/watch?v=JecAk1FAOck
• https://www.youtube.com/watch?v=OGzPmgsI-pQ
• https://www.youtube.com/watch?v=JU767SDMDvA

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