06. Optimizing for Optimistic Scenarios

We have primarily focused on the worst-case scenario when analyzing algorithm efficiency. While this is crucial for preparation, considering all scenarios—including the best and average cases—is vital for choosing the appropriate algorithm. This chapter introduces Insertion Sort, which highlights the value of analyzing non-worst-case performance.

Insertion Sort

Insertion Sort is a third sorting algorithm. Its key feature is that it maintains a sorted subarray on the left side and gradually inserts the next element from the unsorted side into the correct position within the sorted side. The steps are:

1. Temporarily Remove: In each pass-through, starting at index 1, the value at the current index is removed and stored in a temp_value variable, leaving a gap.
2. Shifting Phase: The algorithm looks at the values to the left of the gap (the already sorted portion). It compares the left value to the temp_value.
3. Shift and Move Gap: If the left value is greater than the temp_value, that value is shifted one position to the right, causing the gap to move one position to the left. This shifting continues until it finds a value that is smaller than or equal to the temp_value, or until it reaches the start of the array.
4. Insert: The temp_value is then inserted into the final location of the gap.
5. Repeat: These steps are repeated until the final index has been processed, at which point the array is fully sorted.

Insertion Sort in Action

Let’s apply Insertion Sort to the array $[4,2,7,1,3]$:

First Pass-Through (Index 1, temp_value = 2)

1. Remove 2.
2. Compare 4 (left) to 2.
3. 4 > 2, so shift 4 to the right. Array: $[\text{gap},4,7,1,3]$.
4. Insert 2 into the gap. Array: $[2,4,7,1,3]$.

Second Pass-Through (Index 2, temp_value = 7)

1. Remove 7.
2. Compare 4 (left) to 7.
3. 4 < 7. Shifting stops immediately.
4. Insert 7 back into the gap. Array: $[2,4,7,1,3]$.

Third Pass-Through (Index 3, temp_value = 1)

1. Remove 1.
2. Compare 7, 4, and 2 (from right to left) to 1.
3. All are greater than 1, so 7, 4, and 2 are all shifted right. Array: $[\text{gap},2,4,7,3]$.
4. Insert 1 into the gap. Array: $[1,2,4,7,3]$.

Fourth Pass-Through (Index 4, temp_value = 3)

1. Remove 3.
2. Compare 7 and 4 to 3.
3. 7 > 3, shift 7. 4 > 3, shift 4.
4. Compare 2 to 3. 2 < 3. Shifting stops.
5. Insert 3 into the gap. Array: $[1,2,3,4,7]$. Sorted.

Code Implementation: Insertion Sort

def insertion_sort(array):
	for index in range(1, len(array)):
		temp_value = array[index]
		position = index - 1
		while position >= 0:
			if array[position] > temp_value:
				array[position + 1] = array[position]
				position = position - 1
			else:
				break
		array[position + 1] = temp_value
	return array

The Python implementation uses a for loop for the pass-throughs and a while loop for the shifting phase:

• Outer Loop: for index in range(1, len(array)) controls the pass-throughs, starting from index 1.
  • temp_value = array[index] stores the value being inserted.
  • position = index - 1 starts the pointer at the first element to the left of the gap.
• Inner Loop: while position >= 0: continues shifting as long as the pointer is within the array bounds.
  • Shift: If array[position] > temp_value, the value is shifted right (array[position + 1] = array[position]), and the position pointer moves left (position = position - 1).
  • Stop: The else: break statement ensures the loop stops as soon as a value less than or equal to temp_value is encountered, or when the loop naturally ends by reaching $position=-1$.
• Insert: array[position + 1] = temp_value inserts the stored value into the resulting gap position.

The Efficiency of Insertion Sort

To analyze Insertion Sort’s efficiency, we must count the four types of steps: removals, insertions, comparisons, and shifts.

Worst-Case Analysis: Reverse-Sorted Array

The worst-case scenario for Insertion Sort occurs when the array is sorted in reverse order. In this case, every value must be compared to and shifted past every preceding value.

1. Comparisons and Shifts

• Comparisons: The number of comparisons is $1+2+3+\cdots +(N-1)$. This sum is approximately $\frac{N^2}{2}$. For an array of $N$ elements, the total is roughly $\frac{N^2}{2}$ comparisons.
• Shifts: In the worst case (reverse order), every comparison results in a shift. Thus, shifts also total approximately $\frac{N^2}{2}$.

Combined, comparisons and shifts total approximately $\frac{N^2}{2}+\frac{N^2}{2}=N^2$ steps.

2. Removals and Insertions

• Removals and insertions of the temp_value happen once per pass-through. Since there are $N-1$ pass-throughs, this results in $N-1$ removals and $N-1$ insertions.

3. Total Steps

The total number of steps is: $N^2\text{ (comparisons and shifts)}+(N-1)\text{ (removals)}+(N-1)\text{ (insertions)}=N^2+2N-2\text{ steps}$

Big O Rule: Dropping Lower Orders of N

To express this in Big O notation, we apply the rule of ignoring constants (dropping the 2 and -2), which gives us $O(N^2+2N)$. However, we must apply a second major rule:

Big O notation only takes into account the highest order of $N$ when we have multiple orders added together.

When $N$ becomes large, the highest power of $N$ ($N^2$) dominates the total number of steps so completely that the lower orders ($2N$) are considered trivial.

N	N2	N3	N4
100	10,000	1,000,000	100,000,000

As shown, $N^4$ is vastly more significant than $N^3$, $N^2$, or $N$. By ignoring the lower order $N$ term in $N^2+2N$, we reduce the expression to:

$O(N^2)$

Worst-Case Conclusion

In a worst-case scenario, Insertion Sort has the same time complexity as Bubble Sort and Selection Sort—they are all $O(N^2)$. Although Selection Sort is generally twice as fast in the worst case (due to fewer total steps), the story is not that simple, which brings us back to considering scenarios beyond the worst case.

The Average Case

Focusing only on the worst-case scenario (as we have for Bubble Sort and Selection Sort, both O(N2)) can be misleading. It’s critical to consider the average-case scenario because, based on the bell curve, average scenarios occur most frequently in the real world, while best- and worst-case scenarios are relatively infrequent .

Analyzing Insertion Sort Scenarios

The performance of Insertion Sort varies dramatically based on the input data:

• Worst-Case: Array is sorted in reverse order (e.g., [4,3,2,1]).
  • In every pass-through, the algorithm must compare and shift every value to the left of the temp_value.
  • Steps: N2 total steps (as calculated before). Big O: O(N2).
• Best-Case: Array is already sorted (e.g., [1,2,3,4]).
  • In every pass-through, the algorithm makes just one comparison and zero shifts (since the left element is always smaller than the temp_value).
  • Steps: Approximately N steps. Big O: O(N).
• Average-Case: Array is randomly sorted (e.g., [1,3,4,2]).
  • The shifting phase ends early about half the time. Therefore, in the aggregate, the algorithm compares and shifts about half the data.
  • Steps: Approximately N2/2 steps. Big O: O(N2).

Selection Sort vs. Insertion Sort

In contrast to Insertion Sort, Selection Sort is oblivious to the data order. It takes approximately N2/2 steps in all cases (best, average, and worst) because it lacks a mechanism to end a pass-through early; it must always scan the entire unsorted portion of the array.

Here’s the comparison based on the approximate number of total steps (ignoring lower orders of N):

Algorithm	Best Case (Presorted)	Average Case (Random)	Worst Case (Reverse)
Selection Sort	N2/2	N2/2	N2/2
Insertion Sort	N	N2/2	N2

So, which is better? It depends.

• If your data is likely to be mostly sorted (or already sorted), Insertion Sort is the clear winner due to its O(N) best-case performance.
• If your data is likely to be randomly sorted (the average case), they perform similarly (N2/2 steps).
• If your data is likely to be reverse-sorted (the worst case), Selection Sort is technically faster as it takes N2/2 steps versus Insertion Sort’s N2 steps.

A Practical Example

The problem is to find the intersection—the list of common values—between two arrays, such as $[3,1,4,2]$ and $[4,5,3,6]$, where the intersection is $[3,4]$.

The Initial $O(N^2)$ Implementation

The initial implementation uses nested loops: an outer loop iterates through the first_array, and an inner loop checks every value in the second_array against the current value from the first.

def intersection(first_array, second_array):
    result = []
    for i in first_array:
        for j in second_array:
            if i == j:
                result.append(i)
    return result

If both arrays have size $N$, the algorithm performs $N\times N=N^2$ comparisons. The maximum $N$ insertions into the result array are a lower order term (only $O(N)$). Following the Big O rules (dropping lower orders), the overall time complexity is $O(N^2)$. If the arrays have different sizes, $N$ and $M$, the complexity is $O(N\times M)$.

Crucially, this initial version performs $O(N^2)$ comparisons in all scenarios, regardless of whether the arrays share common values.

The Optimized Solution (Adding a break)

The inefficiency of the first version is that once a match is found, the inner loop continues to run unnecessarily. The optimization is to add a break statement inside the inner loop:

def intersection(first_array, second_array):
    result = []
    for i in first_array:
        for j in second_array:
            if i == j:
                result.append(i)
                break  # Stops the inner loop immediately after a match is found
    return result

Impact on Scenarios:

• Worst-Case Scenario (No shared values): The inner loop must complete every time, as no match is ever found. The number of comparisons remains $N^2$. The Big O complexity remains $O(N^2)$.
• Best/Average-Case Scenario (Shared values exist): By adding the break, the inner loop cuts short once a match is found. This significantly reduces the total number of comparisons and steps, leading to a much faster execution time in practical, common use cases compared to the unoptimized version.

This single-word change provides a significant optimization because it prevents unnecessary work in the common cases where the arrays share elements.