Section 13.5 Insertion Sort
The insertion sort algorithm is a simple and efficient sorting algorithm that builds the final sorted sequence one element at a time. It works by iteratively inserting an element from the unsorted portion of the sequence into its correct position within the sorted portion of the sequence. The algorithm maintains a boundary between the sorted and unsorted portions of the sequence and shifts elements to create space for the insertion.
The insertion sort algorithm works as follows.
- Input: The algorithm takes an unsorted collection or array of elements as input.
- Initialization: Start with the second element (index 1) of the sequence. The first element is considered already sorted.
- Element Selection: Take the current element from the unsorted portion of the sequence.
- Insertion: Compare the current element with the elements in the sorted portion of the sequence, moving from right to left. Shift elements in the sorted portion to the right until you find the correct position for the current element.
- Place Element: Insert the current element into its correct position within the sorted portion of the sequence.
- Repeat: Continue steps 3 to 5, incrementing the position of the current element in the unsorted portion until all elements are placed in their correct positions.
- Termination: Once all elements are inserted in their correct positions, the sorting is complete, and the sequence is now sorted in ascending order.
The insertion sort algorithm’s time complexity can vary based on the initial order of the elements in the sequence. In the best-case scenario (when the sequence is already nearly sorted), insertion sort can have a time complexity of \(O(N)\text{,}\) where \(N\) is the number of elements in teh sequence. In the worst-case scenario (when the sequence is sorted in reverse order), the time complexity is \(O(N^2)\text{.}\) On average, its time complexity is between \(O(N)\) and \(O(N^2)\text{.}\)
Insertion sort is particularly efficient for small sequences and sequences that are nearly sorted, as it requires relatively fewer comparisons and swaps compared to other sorting algorithms like selection sort. While it might not be as fast as more advanced sorting algorithms like merge sort for larger sequences, its simplicity and effectiveness make it a good choice for small-scale sorting tasks or as a building block within more complex algorithms.
In Listing 13.5.1, the
insertionSort(…) function takes an array (arr) as a parameter and sorts it using the insertion sort algorithm. The main method demonstrates how to use the insertion sort function on an array. The insertion sort algorithm builds the sorted portion of the array one element at a time, by iteratively moving elements greater than the current element to one position ahead.After sorting, the output will display the original array and the sorted array.
// InsertionSort.java
import java.util.Arrays;
public class InsertionSort {
// Insertion sort function
static void insertionSort(int[] arr) {
int N = arr.length;
for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;
// Move elements that are greater than the key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arrayToSort = { 12, 11, 13, 5, 6 };
System.out.println("Original array: " + Arrays.toString(arrayToSort));
insertionSort(arrayToSort);
System.out.println("Sorted array: " + Arrays.toString(arrayToSort));
}
}
InsertionSort.javajavac InsertionSort.java java InsertionSort Original array: [12, 11, 13, 5, 6] Sorted array: [5, 6, 11, 12, 13]
