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).
- (4 < 7) that's why we will insert 4 in the sorted part before 7 so the array will be [4,7,12,3]
- (12 > 7) therefore will keep it in the same position so the array will be [4,7,12,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
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
Top comments (1)
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.