Insertion sort algorithm is a simple sorting algorithm that builds the final sorted array or list one item at a time. It is called insertion sort because it inserts each element into its proper place in the sorted array or list.
How Insertion Sort Algorithm Works
Insertion sort algorithm works by taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. The algorithm goes through the list or array multiple times until all elements are in their proper places, which means the list or array is sorted.
Python Implementation of Insertion Sort Algorithm
Here’s an example of implementing the insertion sort algorithm in Python:
lessCopy codedef insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
In the above code, the insertion_sort function takes one argument, arr, which is the list or array to be sorted. The function uses a for loop to go through the list or array multiple times, taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. The while loop compares the key with the previous element in the sorted part of the list or array and inserts the key into its proper place in the sorted part of the list or array.
Example of Insertion Sort Algorithm
Let’s say we have an unsorted list of numbers as follows:
cssCopy codearr = [5, 2, 8, 1, 9, 4]
We want to sort this list using the insertion sort algorithm. We can do this by calling the insertion_sort function with the list arr as an argument:
scssCopy codeinsertion_sort(arr)
After executing this code, the variable arr will contain the sorted list:
csharpCopy code[1, 2, 4, 5, 8, 9]
Advantages and Disadvantages of Insertion Sort Algorithm
The insertion sort algorithm has the following advantages and disadvantages:
Advantages:
- Simple and easy to understand.
- Works well on small datasets.
- Efficient for nearly sorted datasets.
Disadvantages:
- Inefficient for large datasets.
- Time complexity is O(n^2), where n is the number of elements in the list or array.
Conclusion
In conclusion, insertion sort algorithm is a simple sorting algorithm that builds the final sorted array or list one item at a time by taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. Although it is easy to understand and efficient for nearly sorted datasets, it is inefficient for large datasets and has a time complexity of O(n^2). It is useful for sorting small datasets or for educational purposes.
FAQs
- What is the time complexity of insertion sort algorithm?
- The time complexity of insertion sort algorithm is O(n^2), where n is the number of elements in the list or array.
- What is the difference between insertion sort and bubble sort?
- Insertion sort and bubble sort are both simple sorting algorithms, but insertion sort builds the final sorted array or list one item at a time by taking one element at a time from the unsorted part of array.
For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear