Insertion Sort is a simple, yet powerful algorithm for sorting data. The algorithm works by taking one element at a time from an unsorted list and inserting it into a sorted list in the correct position. In this article, we will learn how the Insertion Sort algorithm works and its implementation in Python. Refer the below-animated visualization of insertion sort:
How Insertion Sort Works:
The Insertion Sort algorithm works as follows:
- Take an unsorted list of n elements.
- Pick the first element and insert it into a sorted list.
- Take the next element and insert it into the sorted list in the correct position.
- Repeat step 3 until all elements have been inserted into the sorted list.
Step-by-step Explanation of Insertion sort
Let’s take a closer look at how the algorithm works with an example:
[5, 2, 4, 6, 1, 3]
.We start by picking the first element,
5
, and inserting it into a sorted list [5]
.We then take the second element,
2
, and compare it with 5
. Since 2
is smaller than 5
, we swap them, and the sorted list becomes [2, 5]
.We then take the third element,
4
, and insert it into the sorted list.We compare
4
with 5
and swap them, giving us [2, 4, 5]
.We continue this process until we have a sorted list of all elements.
How to implement insertion sort in Python
def insertionSort(arrayToSort): """ Complexity: best : O(n) average : O(n^2) worst : O(n^2) parameters: arrayToSort: Array to be sorted returns: sorted array """ for i in range(1, len(arrayToSort)): j = i while j > 0 and arrayToSort[j] < arrayToSort[j - 1]: arrayToSort[j], arrayToSort[j - 1] = arrayToSort[j - 1], arrayToSort[j] j -= 1 return arrayToSort if __name__ == "__main__": array = [2, 5, 1, 5, 8, 9, 0, 10] print(insertionSort(array))
Conclusion:
In summary, Insertion Sort is a simple and efficient algorithm for sorting data. It works by inserting each element into a sorted list in the correct position. While Insertion Sort is less efficient than Merge Sort for large datasets, it can be more efficient than Bubble Sort for small datasets. It is important to choose the appropriate sorting algorithm depending on the size of the dataset and the specific use case.
0 Comments