Insertion Sort is a simple sorting algorithm that works by dividing the array into a sorted and an unsorted portion. It iterates through the unsorted portion, selecting one element at a time and inserting it into its correct position in the sorted portion. This process continues until the entire array is sorted.
Here’s how Insertion Sort works step by step:
Initialization:
Start with an unsorted array of elements.
Set the first element as the sorted portion (as a single-element sorted array) and the remaining elements as the unsorted portion.
Iteration:
Iterate through each element in the unsorted portion of the array, starting from the second element (index 1).
For each element, compare it with the elements in the sorted portion from right to left until a smaller element is found or until the beginning of the sorted portion is reached.
Insertion:
Once a smaller element is found, shift the elements in the sorted portion to the right to make room for the current element.
Insert the current element into its correct position in the sorted portion.
Repeat:
Continue the iteration and insertion steps until all elements in the unsorted portion have been processed.
Completion:
After the iteration is complete, the entire array is sorted.
Here’s an example to illustrate the Insertion Sort algorithm:
Unsorted array: [5, 2, 4, 6, 1, 3]
1st iteration:
Start with the second element, 2.
Compare it with the first element, 5. Since 2 is smaller, shift 5 to the right.
Insert 2 in the first position of the sorted portion.
Sorted portion: [2, 5] | Unsorted portion: [4, 6, 1, 3]
2nd iteration:
Consider the next element, 4.
Compare it with the elements in the sorted portion (5, 2) and shift them to the right if they are greater.
Insert 4 in the correct position within the sorted portion.
Sorted portion: [2, 4, 5] | Unsorted portion: [6, 1, 3]
3rd iteration:
Consider the next element, 6.
Since it is greater than all elements in the sorted portion, no shifting is needed.
Insert 6 at the end of the sorted portion.
Sorted portion: [2, 4, 5, 6] | Unsorted portion: [1, 3]
Continue the process until all elements in the unsorted portion are processed.
Final sorted array: [1, 2, 3, 4, 5, 6]
Insertion Sort has a time complexity of O(n^2) in the worst case and performs well for small or partially sorted arrays. It is an in-place sorting algorithm, meaning it does not require additional memory beyond the input array.
Here’s the Algorithm for Insertion Sort:
Start with an unsorted array of elements.
Iterate through each element in the unsorted portion, starting from the second element (index 1).
For each element, compare it with the elements in the sorted portion from right to left until a smaller element is found or until the beginning of the sorted portion is reached.
Once a smaller element is found, shift the elements in the sorted portion to the right to make room for the current element.
Insert the current element into its correct position in the sorted portion.
Repeat steps 2-4 until all elements in the unsorted portion have been processed.
The array is now sorted.
Here’s a step-by-step breakdown of the algorithm:
Input: Unsorted array
For i = 1 to n-1:
Set currentElement = array[i]
Set j = i-1
While j >= 0 and array[j] > currentElement:
Shift array[j] to the right by 1 position
Decrement j by 1
Insert currentElement at array[j+1]
Repeat steps 1-3 until i reaches the end of the array
Output: Sorted array
This algorithm performs an in-place sorting, meaning it rearranges the elements within the given array without requiring additional memory space. The time complexity of Insertion Sort is O(n^2) in the worst case, where n is the number of elements in the array.
Insertion Sort application
Insertion Sort is a simple sorting algorithm that is efficient for small data sets or partially sorted data. While it may not be the most efficient algorithm for large data sets, it still has some practical applications in various scenarios. Here are a few applications where Insertion Sort can be useful:
- Small Data Sets: Insertion Sort performs well for small data sets or when the input size is relatively small. It has a relatively low overhead compared to more complex sorting algorithms, making it a good choice for small-scale sorting tasks.
- Partially Sorted Data: If the input data is already partially sorted or nearly sorted, Insertion Sort has an advantage. It can take advantage of the partially sorted nature of the data and complete the sorting efficiently, making it suitable for scenarios where data is frequently added to an already sorted list.
- Online Sorting: Insertion Sort is an online algorithm, meaning it can efficiently sort data as it arrives in a streaming fashion. This makes it suitable for scenarios where data is continuously generated or streamed in real-time, and immediate sorting is required.
- Teaching and Learning: Insertion Sort is often used as an introductory algorithm to teach basic sorting concepts. Its simplicity and ease of implementation make it a valuable learning tool to understand sorting algorithms and their properties.
- Auxiliary Sorting Algorithm: Insertion Sort can be used as an auxiliary algorithm within other sorting algorithms. For example, algorithms like QuickSort and TimSort may switch to Insertion Sort for small subarrays or as a final pass to improve efficiency.
It’s important to note that while Insertion Sort has its applications, there are more efficient sorting algorithms available for larger data sets, such as Merge Sort or QuickSort. The choice of sorting algorithm depends on the specific requirements and characteristics of the data being sorted.
Complexity
The time and space complexity of Insertion Sort can be described as follows:
Time Complexity:
- Best Case: O(n)
- Average Case: O(n^2)
- Worst Case: O(n^2)
In the best case scenario, when the input data is already sorted, Insertion Sort performs efficiently with a linear time complexity of O(n). This is because there is no need for swapping elements or shifting values, and each element is compared to its predecessor only once.
However, in the average and worst case scenarios, Insertion Sort has a quadratic time complexity of O(n^2). This is because for each element in the unsorted part of the array, it needs to compare it with all previous sorted elements and potentially shift them to make room for the current element. As the input size grows, the number of comparisons and shifts increases exponentially, resulting in a slower performance.
Space Complexity: Insertion Sort has a space complexity of O(1) since it operates directly on the input array without requiring additional data structures. It performs in-place sorting by rearranging the elements within the array itself, without allocating extra memory.
Overall, Insertion Sort is considered an efficient algorithm for small data sets or partially sorted data, but it becomes less efficient as the input size grows. For larger data sets, more advanced sorting algorithms with better time complexity, such as Merge Sort or QuickSort, are generally preferred.
An example of Insertion Sort implemented in Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i – 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
Example usage
array = [7, 2, 4, 1, 5, 3]
insertion_sort(array)
print(array)
In this code, the insertion_sort function takes an array arr as input and performs the Insertion Sort algorithm on it. It starts by iterating through the array, starting from the second element (index 1), because the first element is considered already sorted. For each element, it compares it with the previous elements in the sorted part of the array and shifts them to the right until it finds the correct position for the current element.
The key variable holds the current element being compared, and the j variable is used to traverse the sorted part of the array from right to left. The while loop compares key with each element in the sorted part and shifts them if necessary. Once the correct position is found, the key is inserted at that position.
After calling the insertion_sort function with an example array, the sorted array is printed as output: [1, 2, 3, 4, 5, 7].
About The Author
