Working of Insertion Sort Algorithm
The insertion sort algorithm follows an interesting approach to sorting elements in an array. Let's understand the step-by-step working of the algorithm:
1. Start with the first element of the array & consider it as already sorted.
2. Move to the next element, which becomes the "key" element. Compare the key element with the elements in the sorted portion of the array, starting from right to left.
3. If an element in the sorted portion is greater than the key element, shift that element one position to the right. Continue shifting elements until you find an element smaller than or equal to the key element or reach the beginning of the array.
4. Insert the key element into the correct position within the sorted portion of the array, which is the position where the shifting stopped.
5. Repeat steps 2-4 for all the remaining unsorted elements until the entire array is sorted.
At each iteration, the algorithm maintains two subarrays:
- The sorted subarray, which contains the elements that have been inserted into their correct positions.
- The unsorted subarray, which contains the remaining elements that need to be processed.
As the algorithm progresses, the sorted subarray grows, & the unsorted subarray shrinks until all elements are inserted into their proper positions, resulting in a fully sorted array.
Note: The insertion sort algorithm performs in-place sorting, which means it modifies the original array without requiring additional storage space. It efficiently handles small datasets and arrays that are nearly sorted, as it requires fewer element comparisons and shifts in such cases.
Insertion Sort Algorithm
Now we know the working principle of the insertion sort algorithm, let's discuss its algorithm in step by step manner:
1. Start with an unsorted array of elements.
2. Set a loop variable i to 1, representing the current element being processed.
3. While i is less than the length of the array:
a. Set a variable key to the value of the current element at index i.
b. Set a variable j to i - 1, representing the index of the last element in the sorted portion.
c. While j is greater than or equal to 0 and the element at index j is greater than key:
- Shift the element at index j one position to the right.
- Decrement j by 1.
d. Insert the key element at index j + 1, which is the correct position in the sorted portion.
e. Increment i by 1 to move to the next element.
4. Repeat steps 3a-3e until i reaches the end of the array.
5. The array is now sorted.
Let’s see how the insertion sort algorithm can be implemented in Java:
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
In this implementation, we use a for loop to iterate through the array starting from index 1. We set the current element as the key and compare it with the elements in the sorted portion of the array. We shift the elements greater than the key to the right using a while loop until we find the correct position for the key element. Finally, we insert the key element into its correct position.
Simple Java Program to Sort an Array Using Insertion Sort Algorithm
Let's see how we can implement the insertion sort algorithm in a complete Java program to sort an array:
public class InsertionSortExample {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 1, 6};
System.out.println("Original array:");
printArray(arr);
insertionSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
You can also try this code with Online Java Compiler
In this program:
1. We define the `insertionSort` method that takes an integer array as input. It implements the insertion sort algorithm as described in the previous section.
2. We define a helper method `printArray` that takes an integer array & prints its elements.
3. In the `main` method:
- We create an unsorted integer array `arr`.
- We print the original array using the `printArray` method.
- We call the `insertionSort` method to sort the array.
- We print the sorted array using the `printArray` method.
Output
Original array:
5 2 8 12 1 6
Sorted array:
1 2 5 6 8 12
The program shows how to use the insertion sort algorithm to sort an array of integers. The `insertionSort` method modifies the original array in place, which results in a sorted array.
You can modify the `arr` array in the `main` method to test the insertion sort algorithm with different input arrays.
Time and Space Complexities
Time Complexity
Worst Case: O(n^2)
- In the worst case, when the array is reverse-sorted, the insertion sort algorithm requires the maximum number of comparisons and shifts.
- For each element, it needs to compare and shift all the previous elements, resulting in a quadratic time complexity.
Average Case: O(n^2)
- On average, the insertion sort algorithm still requires a quadratic number of comparisons and shifts.
- The number of comparisons and shifts depends on the initial order of the elements in the array.
Best Case: O(n)
- In the best case, when the array is already sorted, the insertion sort algorithm performs only one comparison for each element.
- It requires a linear number of comparisons, resulting in a time complexity of O(n).
The time complexity of insertion sort makes it less efficient for large datasets compared to more advanced sorting algorithms like Merge Sort or Quick Sort. However, it performs well for small arrays or arrays that are nearly sorted.
Space Complexity
- The space complexity of insertion sort is O(1), meaning it requires constant extra space.
- Insertion sort is an in-place sorting algorithm, as it modifies the original array without requiring any significant additional storage.
- It only uses a few variables to keep track of the current element, the key, and the position for comparison and shifting.
The constant space complexity is one of the advantages of insertion sort, as it doesn't consume extra memory proportional to the input size.
Note: Always remember that the actual running time of the insertion sort algorithm can vary depending on the specific implementation and the programming language used. However, the general time and space complexity analysis is similar to most implementations.
Insertion Sort Applications
1. Small datasets: Insertion sort is often used when the input size is small. For small arrays, insertion sort can be faster than more complex algorithms like Merge Sort or Quick Sort due to its simplicity and low overhead. In such cases, the constant factors associated with insertion sort can make it a practical choice.
2. Nearly sorted arrays: Insertion sort performs efficiently when the input array is already nearly sorted. If the array is almost in the correct order with only a few elements out of place, insertion sort can quickly sort the array with a minimal number of comparisons and shifts. It takes advantage of the existing order and requires fewer iterations to sort the array fully.
3. Hybrid sorting algorithms: Insertion sort is commonly used as a base case or subroutine in hybrid sorting algorithms. For example, in the Timsort algorithm (used in Java's Arrays.sort() and Python's sorted()), insertion sort is applied to small subarrays before merging them. This hybrid approach combines the strengths of insertion sort for small arrays with the efficiency of Merge Sort for larger arrays.
4. Online algorithms: Insertion sort is an online algorithm, which means it can sort elements as they arrive without requiring the entire array to be available upfront. This property makes insertion sort useful in scenarios where data is streaming or arriving in real-time, and sorting needs to be performed incrementally.
5. Educational purposes: Insertion sort is often taught in introductory computer science courses and used for educational purposes. Its simplicity and intuitive nature make it a good starting point for understanding sorting algorithms and their implementation. It serves as a foundation for learning more advanced sorting techniques.
6. In-place sorting: Insertion sort is an in-place sorting algorithm, meaning it sorts the array without requiring additional storage space. This can be useful when memory is limited, or the cost of allocating extra memory is high. In-place sorting is also very useful when you are dealing with large datasets that cannot fit entirely in memory.
Frequently Asked Questions
Is insertion sort stable?
Yes, insertion sort is a stable sorting algorithm. It maintains the relative order of equal elements during the sorting process.
Can insertion sort handle duplicate elements?
Yes, insertion sort can handle arrays with duplicate elements. It preserves the relative order of equal elements, ensuring stability.
Is insertion sort an in-place sorting algorithm?
Yes, insertion sort is an in-place sorting algorithm. It sorts the array without requiring additional storage space.
Conclusion
In this article, we discussed the insertion sort algorithm, a simple but efficient sorting technique, in detail. We looked into its working principle, implemented it using Java code, and analyzed its time and space complexities. We also discussed its applications and advantages in specific scenarios. Insertion sort, with its simplicity and efficiency for small and nearly sorted arrays, especially when memory is limited or the input size is small.
You can also check out our other blogs on Code360.
135+ registered 
