Chapter 2.1

Insertion Sort

Insertion Sort: A Historical Perspective

Insertion sort is one of the earliest algorithms used for sorting, often taught as an introductory algorithm due to its simplicity and intuitive approach. It is believed to have been first documented by John Mauchly in the late 1940s, though the concept is older and has likely been used informally for hundreds of years. Mauchly, a co-developer of the ENIAC (one of the first general-purpose computers), described the algorithm in the context of machine sorting. The algorithm itself is closely related to the way humans sort playing cards by repeatedly inserting unsorted cards into the correct position within a hand.

Though simple, insertion sort is inefficient on large lists compared to more advanced algorithms such as quicksort or merge sort, but its ease of implementation makes it useful for small datasets or as a subroutine in more complex algorithms.

---

Insertion Sort: Algorithm Overview

Insertion sort works by building a sorted list one element at a time. The algorithm iterates through the list, taking each element and placing it into its correct position relative to the already sorted elements.

It operates similarly to the way you might sort playing cards in your hand. Starting with an empty hand, you take each card from the deck and insert it into the correct position in your hand.

---

Pseudocode for Insertion Sort

#Algorithm: InsertionSort(arr)
Input: A list of elements 'arr'
Output: The list sorted in increasing order

1. For i = 1 to length(arr) - 1:
    a. Set current_element = arr[i]
    b. Set j = i - 1
    c. While j >= 0 and arr[j] > current_element:
        i. Shift arr[j] to arr[j + 1]
        ii. Decrement j
    d. Insert current_element at arr[j + 1]
2. End

Explanation of Pseudocode:

• Step 1: We start from the second element (index 1) and assume the first element is already sorted.

• Step 2: For each element, we compare it with the elements before it in the list.

• Step 3: We shift elements to the right if they are larger than the current element.

• Step 4: Once the correct position is found, we place the current element in that position.

---

Python Code for Insertion Sort

def insertion_sort(arr):
    # Traverse from the second element to the end of the list
    for i in range(1, len(arr)):
        current_element = arr[i]  # Current element to be inserted
        j = i - 1       
        # Shift elements of arr[0..i-1], 
        # that are greater than current_element, 
        # to one position ahead
        while j >= 0 and arr[j] > current_element:
            arr[j + 1] = arr[j]
            j -= 1
        # Insert the current element into its correct position
        arr[j + 1] = current_element
    return arr

# Example usage:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

To convert the insertionsort function into an object-oriented (OOP) format, we can create a class, for example, called Sorter. The sorting function will be a method within the class. This way, the sorting function is encapsulated within a class, adhering to the principles of object-oriented programming. Here's how you can do it:

class Sorter:
    def __init__(self, data):
        # Initialize the class with the list to be sorted
        self.data = data

    def insertion_sort(self):
        n = len(self.data)
        if n < 1:
            return self.data
        for i in range(n):
            j = i
            while j > 0 and self.data[j] < self.data[j - 1]:
                # Swap elements
                self.data[j], self.data[j - 1] = self.data[j - 1], self.data[j]
                j -= 1
        return self.data

# Example usage:
L = [64, 25, 12, 22, 11]
sorter = Sorter(L)
sorted_list = sorter.insertion_sort()
print(sorted_list)

Explanation:

1. Class Sorter: This class will represent the sorting functionality.

   • __init__ Method: Initializes the class with a list (data) that needs to be sorted.

   • insertion_sort Method: Implements the insertion sort algorithm and sorts the list stored in self.data.

2. Example Usage:

   • An instance of the Sorter class is created with the unsorted list L.

   • The insertion_sort method is called on this instance to sort the list, and the result is printed.

How the Python Code Works:

1. Outer Loop (for i in range(1, len(arr))): This starts at the second element of the array (index 1) and moves toward the end. We treat the portion of the array before the current element as already sorted.

2. Inner Loop (while j >= 0 and arr[j] > current_element): This loop compares the current element to the previous elements in the sorted part of the list. If the current element is smaller than an earlier element, the earlier element is shifted to the right.

3. Insertion: Once the correct position is found, the current element is placed into that position.

Example Walkthrough:

Consider the array [12, 11, 13, 5, 6]:

• Step 1: Start with 11 (index 1). Compare with 12, and since 11 < 12, shift 12 to the right and insert 11 at index 0.

  • Array becomes [11, 12, 13, 5, 6].

• Step 2: Move to 13 (index 2). No need to shift since 13 is already in the correct position.

  • Array remains [11, 12, 13, 5, 6].

• Step 3: Move to 5 (index 3). Compare with 13, 12, and 11, shifting them to the right, and insert 5 at index 0.

  • Array becomes [5, 11, 12, 13, 6].

• Step 4: Move to 6 (index 4). Compare with 13, 12, and 11, shift them to the right, and insert 6 at index 1.

  • Array becomes [5, 6, 11, 12, 13].

---

Time Complexity of Insertion Sort

• Best Case (Already Sorted List):

  • In this scenario, no shifting is required, and the algorithm only performs $O({n})$ comparisons. This happens when the input list is already sorted.

$$1 + 1 + 1 + \cdots + 1 \quad (\text{n times}) = n = O(n)$$

• Worst Case (Reversed List):

  • In the worst case, the algorithm has to compare and shift every element, resulting in a time complexity $O({n^2})$ . This occurs when the input list is in reverse order.

$$n + (n-1) + (n-2) + \cdots + 1 = n(n+1)/2 = O(n^2)$$

• Average Case:

  • On average, the time complexity is $O({n^2})$ as the algorithm may need to shift elements multiple times for each insertion.

$$n + (n-1) + (n-2) + \cdots + 1 = n(n+1)/2 = O(n^2)$$

---

Why Insertion Sort Can Be Useful

Despite its $O({n^2})$ time complexity, insertion sort has several advantages in certain situations:

1. Small Data Sets: For small datasets, insertion sort is often faster than more complex algorithms like quicksort or mergesort because of its low overhead.

2. Nearly Sorted Data: If the input list is already "almost" sorted (few elements are out of order), insertion sort can perform exceptionally well, approaching O(n) time complexity.

3. Stable Sort: Insertion sort is stable, meaning it preserves the relative order of elements with equal keys.

4. In-Place Sorting: It requires a constant amount of extra memory space, making it space-efficient.

---

Optimizing Insertion Sort with Binary Search

An optimization to the insertion sort is to use binary search to find the correct position where the current element should be inserted. This reduces the number of comparisons required to find the correct insertion point, but it doesn't reduce the number of shifts, so the overall time complexity remains $O({n^2})$.

---

Conclusion

Insertion sort is an intuitive and simple sorting algorithm ideal for small or nearly sorted datasets. Its quadratic time complexity makes it inefficient for large datasets, but its simplicity and low overhead can make it faster than more complex algorithms in specific situations.