Understanding Insertion Sort: A Comprehensive Guide
Written on
Chapter 1: Introduction to Insertion Sort
Insertion sort functions similarly to the way one might arrange a hand of cards before a game. Typically, you'd want to sort these cards in ascending order. Let’s illustrate this process using an example with the unsorted array [8, 3, 7, 1, 4, 6].
We start with the first card, 8, and compare it to the next card, which is 3. Since 3 is less than 8, we swap them, resulting in [3, 8, 7, 1, 4, 6]. Next, we check 8 again and see it is still larger than the card before it, so no action is taken. The array remains [3, 8, 7, 1, 4, 6].
Next, we take the third card, 7. Comparing it with the cards to its left (3 and 8), we find that 7 should fit between them. We move 8 to the right and insert 7 in its proper position, resulting in [3, 7, 8, 1, 4, 6].
Moving on to the fourth card, 1, which is smaller than all the cards on its left, we shift all the cards one position to the right to make space for 1 at the beginning. This updates the array to [1, 3, 7, 8, 4, 6].
For the fifth card, 4, we notice it should be placed between 3 and 7. Thus, we shift 7 to the right, allowing us to insert 4 in the correct spot, resulting in [1, 3, 4, 7, 8, 6].
Finally, we examine the sixth card, 6. It is smaller than 7 but larger than 4, so we shift 7 to the right and position 6 correctly. This gives us the final sorted array: [1, 3, 4, 6, 7, 8].
For a clearer understanding of these steps, refer to the diagram below that visually illustrates the sorting process.
Section 1.1: Implementing Insertion Sort in JavaScript
With a solid grasp of how the card sorting analogy translates into the algorithm, let's implement it in JavaScript. Here’s a simple function for insertion sort:
function insertionSort(arr) {
// Loop through each element starting from the second
for (let j = 1; j < arr.length; j++) {
let current = arr[j]; // Current element to be positioned
let i = j - 1; // Pointer for the sorted section
// Shift elements to the right to make room for current
while (i >= 0 && arr[i] > current) {
arr[i + 1] = arr[i]; // Shift element to the right
i--; // Move pointer left
}
arr[i + 1] = current; // Place current in its sorted position
}
return arr; // Return the sorted array
}
Now, let's detail the steps of the sorting process:
- Initial array: [8, 3, 7, 1, 4, 6]
- Iteration 1: Key = 3; shift 8 right → [3, 8, 7, 1, 4, 6]
- Iteration 2: Key = 7; shift 8 right → [3, 7, 8, 1, 4, 6]
- Iteration 3: Key = 1; shift 8, 7, and 3 right → [1, 3, 7, 8, 4, 6]
- Iteration 4: Key = 4; shift 8, 7, and 3 right → [1, 3, 4, 7, 8, 6]
- Iteration 5: Key = 6; shift 8 and 7 right → [1, 3, 4, 6, 7, 8]
The sorted array now reads: [1, 3, 4, 6, 7, 8].
Section 1.2: Time Complexity of Insertion Sort
Worst-Case Scenario (O(n²))
In the worst-case situation, when the array is in complete disorder, insertion sort exhibits a quadratic time complexity. Each element in the unsorted section must be compared to every element in the sorted section, potentially leading to numerous shifts. This results in a significant increase in the time required as the array size grows, specifically following the formula n².
Best-Case Scenario (O(n))
Conversely, if the array is nearly sorted, insertion sort performs linearly, with time complexity of O(n). This condition minimizes the number of necessary comparisons and shifts, allowing for efficient sorting.
Average-Case Scenario
For an average case, with randomly ordered elements, insertion sort typically performs better than in the worst-case but worse than in the best-case. The average complexity tends to align closer to the worst-case scenario, especially with larger datasets, due to the potential for more comparisons and shifts.
Understanding these time complexities is crucial for predicting insertion sort's performance based on the initial state of the array. While insertion sort can be quite efficient for nearly sorted data, it may slow significantly for highly unsorted arrays.
Chapter 2: Visual Learning with YouTube
To further enhance your understanding, check out the following videos:
The first video, Insertion Sort in 2 Minutes, provides a quick overview of the algorithm's mechanics.
The second video, Learn Insertion Sort in 7 Minutes, offers a more in-depth explanation and demonstration of the insertion sort process.