An Interest In:
Web News this Week
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
- April 19, 2024
- April 18, 2024
June 21, 2021 10:54 pm GMT
Original Link: https://dev.to/ayabouchiha/insertion-sort-algorithm-2gj3
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).
- (4 < 7) that's why we will insert 4 in the sorted part before 7so 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
Original Link: https://dev.to/ayabouchiha/insertion-sort-algorithm-2gj3
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To