Insertion sort is an important method in organizing data, especially good at sorting small groups of information. It works by dividing a list into two parts: one that’s already sorted and one that’s not. Just like when you sort playing cards, it takes each item from the unsorted section and finds the right spot for it in the sorted section.
Insertion Sort Algorithm
The Insertion Sort Algorithm sorts a list by taking one item at a time and putting it in its correct place among those already sorted. Imagine it like sorting a hand of playing cards: you start with the second card and compare it to the first. If it’s smaller, you move it before the first card. Then, you move to the next card and do the same, always comparing with the sorted cards and placing it where it fits. This way, bit by bit, the whole list gets sorted. It’s simple and works well when the list is already almost sorted or is short.
Working of Insertion Sort Algorithm
Let’s explore how the Insertion Sort algorithm works using the array { 13, 12, 18, 2, 5 }:
Initial Array:
- [ 13, 12, 18, 2, 5 ]
First Pass:
- Compare the first two elements (13 and 12). Since 13 is greater than 12, they are swapped to maintain ascending order.
- New array: [ 12, 13, 18, 2, 5 ]
Second Pass:
- Move to the next element (18) and compare it with its predecessors. It’s already in the correct position relative to 12 and 13, so no swaps are needed.
- Array remains: [ 12, 13, 18, 2, 5 ]
Third Pass:
The focus shifts to the fourth element (2), which is compared with its predecessors to find its rightful spot.
- Initial comparison with 18 shows 2 is smaller, swap 2 and 18: [ 12, 13, 2, 18, 5 ]
- Continuing the comparison, 2 is also smaller than 13, leading to another swap: [ 12, 2, 13, 18, 5 ]
- Finally, 2 is compared with 12 and, being smaller, is swapped again, positioning it correctly at the array’s start: [ 2, 12, 13, 18, 5 ] Now, 2 is it correct position.
Fourth Pass:
Attention now turns to the last element (5).
- Initially, 5 is compared with 18 and found to be smaller, swap 18 and 5: [ 2, 12, 13, 5, 18 ]
- The comparison continues with 13, and since 5 is smaller, another swap occurs: [ 2, 12, 5, 13, 18 ]
- Lastly, 5 is compared with 12, and being smaller, necessitates the final swap, placing it in its proper position: [ 2, 5, 12, 13, 18 ]
- This final pass ensures that 5 is inserted between 2 and 12, completing the sorting process with the array now fully sorted.
Finally, the array is sorted completely.
Implementation of Insertion Sort Algorithm
Java Program for Insertion Sort
// *** JAVA IMPLEMENTATION ***
void insertionSort(int arr[]){
int n = arr.length;
for (int i = 1; i < n; i++) { // Start from 1 as arr[0] is always sorted
int currentElement = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than value,
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Finally place the Current element at its correct position.
arr[j + 1] = currentElement;
}
}
public static void main(String args[]){
int arr[] = { 9, 6, 7, 2, 5, 8};
insertionSort(arr);
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
}
Output:
2 5 6 7 8 9
C++ Program for Insertion Sort
// *** C++ IMPLEMENTATION ***
void insertionSort(int arr[], int n){
for (int i = 1; i < n; i++){ // Start from 1 as arr[0] is always sorted
Int currentElement = arr[i];
Int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement){
arr[j + 1] = arr[j];
j = j - 1;
}
// Finally place the Current element at its correct position.
arr[j + 1] = currentElement;
}
}
int main(){
int arr[] = { 9, 6, 7, 2, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
for (i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output:
2 5 6 7 8 9
C Program for Insertion Sort
// *** C IMPLEMENTATION ***
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) { // Start from 1 as arr[0] is always sorted
int currentElement = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Finally place the Current element at its correct position.
arr[j + 1] = currentElement;
}
}
int main(){
int arr[] = { 9, 6, 7, 2, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output:
2 5 6 7 8 9
C# Program for Insertion Sort
// *** C# IMPLEMENTATION ***
void insertionSort(int[] arr){
int n = arr.Length;
for (int i = 1; i < n; ++i) { // Start from 1 as arr[0] is always sorted
int currentElement = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Finally place the Current element at its correct position.
arr[j + 1] = currentElement;
}
}
public static void Main(){
int[] arr = { 12, 11, 13, 5, 6 };
insertionSort(arr);
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
}
Output:
2 5 6 7 8 9
Python Program for Insertion Sort
# *** PYTHON IMPLEMENTATION ***
def insertionSort(arr):
# Start from 1 as arr[0] is always sorted
for i in range(1, len(arr)):
currentElement = arr[i]
# Move elements of arr[0..i-1], that are greater than key,
# to one position ahead of their current position
j = i-1
while j >= 0 and arr[j] > currentElement :
arr[j + 1] = arr[j]
j -= 1
# Finally place the Current element at its correct position.
arr[j + 1] = currentElement
# Driver code to test above
arr = [9, 6, 7, 2, 5, 8]
insertionSort(arr)
for i in range(len(arr)):
print ("% d" % arr[i])
Output:
2 5 6 7 8 9
PHP Program for Insertion Sort
// *** PHP IMPLEMENTATION ***
<?php
function insertionSort(&$arr, $n) {
for ($i = 1; $i < $n; $i++) { // Start from 1 as arr[0] is always sorted
$currentElement = $arr[$i];
$j = $i-1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while ($j >= 0 && $arr[$j] > $currentElement) {
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
}
// Finally place the Current element at its correct position.
$arr[$j + 1] = $currentElement;
}
}
$arr = array(9, 6, 7, 2, 5, 8);
$n = sizeof($arr);
insertionSort($arr, $n);
for ($i = 0; $i < $n; $i++)
echo $arr[$i]." ";
?>
Output:
2 5 6 7 8 9
Complexity Analysis of Insertion Sort Algorithm
Time Complexity of Insertion Sort Algorithm
- Best Case (O(N)): This happens when the array is already sorted. Only one comparison per element is needed, making the process quick.
- Worst Case (O(N²)): This occurs when the array is sorted in reverse order. Each element needs to be compared with all others, leading to a lot of comparisons and shifts.
- Average Case (O(N²)): Typically, elements are in a random order, and the algorithm still requires a significant number of comparisons and shifts, similar to the worst case.
Space Complexity of Insertion Sort Algorithm
Space Complexity of Insertion Sort is (O(1)) as Insertion Sort uses a constant amount of space regardless of the array size, making it a space-efficient algorithm.
Applications of Insertion Sort Algorithm
Here are some applications where Insertion Sort shines:
- Small Datasets: Its efficiency in handling small arrays makes it an ideal choice for sorting limited amounts of data, where its quadratic time complexity doesn’t pose a significant performance issue.
- Nearly Sorted Data: Insertion Sort excels when the dataset is already close to being sorted, requiring minimal shifts to arrange the elements, thereby optimizing performance in such contexts.
- Real-time Data: Given its in-place and stable nature, Insertion Sort is well-suited for real-time processing where data arrives in increments and needs to be sorted on the fly without consuming additional memory.
- Stable Sorting Requirements: In scenarios where maintaining the relative order of equal elements is crucial, Insertion Sort’s stability ensures that identical values retain their original sequence post-sorting.
- Space Constraints: Its in-place algorithmic nature means that Insertion Sort doesn’t require extra space beyond the original dataset, making it a good option for environments with memory limitations.
Characteristics of Insertion Sort Algorithm
- Simple Implementation: The insertion sort in data structure is straightforward to implement, making it a good choice for small datasets and introductory programming exercises.
- Adaptive: It performs well with partially sorted arrays, requiring fewer shifts, which makes it more efficient in such scenarios.
- Stable: Insertion sort maintains the relative order of equal elements, ensuring that no rearrangement occurs for similar values.
- In-Place: It sorts the array by modifying it directly, requiring no additional space for another array, leading to a space complexity of O(1).
- Online: Insertion sort can sort a list as it receives it, making it suitable for real-time data processing where the complete dataset is not known in advance.
- Best for Small Datasets: Due to its O(N²) time complexity, it is most suited for small arrays. Its efficiency decreases as the dataset size increases.
- Quadratic Time Complexity: In the average and worst cases, it has a quadratic time complexity, which is less efficient compared to more advanced sorting algorithms for large datasets.
Conclusion
- Insertion sort in data structure is a fundamental algorithm, ideal for sorting small datasets.
- Its simplicity and in-place sorting make it a preferred choice for introductory programming tasks.
- However, the time complexity of Insertion Sort can be a drawback, particularly for large arrays, where it averages and worst-case scenarios result in (O(n^2)) complexity.
- Despite this, its space efficiency is notable, requiring only a constant amount (O(1)) of additional storage space.
- Insertion Sort’s adaptability, stability, and ease of implementation underscore its utility in specific scenarios, despite the limitations imposed by its quadratic time complexity.
