12.1. Insertion Sort

So, let us continue with a discussion of sorting, and look at another simple sorting algorithm. There are many motivations for sorting; starting from searching, to removing duplicates, to computing some statistical properties, such as frequency tables, and so on.

This chunk introduces the concept of sorting and why it is essential. Sorting is used in many areas, such as searching for items, eliminating duplicate entries, and calculating statistics. In this context, we are discussing the Insertion Sort algorithm, which is one of the simple sorting methods.

Imagine you have a collection of books, and you want to arrange them in alphabetical order. Sorting helps you locate a specific book quickly, similar to how algorithms help organize data efficiently.

So, the second strategy to sort this bunch of exam papers would be the following. You take the top-most paper in this stack that you have, and create a new stack. Now you take the second paper and compare it to the first paper. If the mark is bigger, you put it above; if the mark is smaller, you put it below.

In this explanation of the Insertion Sort process, we start by taking one item (in this case, the top-most paper) to create a new sorted stack. We then compare subsequent items to this first one: if the next item is larger, it goes on top; if smaller, it goes below, gradually building a sorted stack as we repeat this with each paper.

Think of sorting a deck of cards: you take one card to start and then place other cards either above or below it based on their rank. You repeat this process until all cards are neatly arranged.

Supposing we have a roll of an array of the unsorted elements. We start with the very first element namely 74, taking it and starting a new stack. We then look at the next element, 32, and since it is smaller, it should go to the left of 74.

Here, we illustrate how to apply the Insertion Sort algorithm with a practical example. Starting with the first element (74), we place it in our sorted section. When the next item (32) is examined, it is found to be smaller, prompting us to place it to the left of 74, maintaining the order as we add more elements.

Consider sorting a stack of index cards with people’s names written on them. You take the first card and then compare the next ones, placing them in the correct spot based on alphabetical order. As you proceed, the index perfectly reflects an organized list of names.

At each step, we pick up the next element and insert it into the already sorted segments that we have created with all the previous elements. This is called the insertion step.

This chunk clarifies that the core of Insertion Sort involves picking the next unsorted element and finding the correct position for it within the already sorted elements. The process continues until all elements are in their proper order, which is key to how Insertion Sort works effectively.

Imagine you're organizing your email inbox. You can picture it as a sorted list where every new email must be placed in the right order within your existing emails. As you go through each new message, you decide exactly where it fits into your organized list.

This is a straightforward iterative implementation again. We start with position 1 and then look backwards, continuously moving left as long as the value we are looking at is smaller than the value to its left.

The iterative implementation of Insertion Sort begins with the second element (position 1) and compares it with previous elements. During this process, if we find a smaller value, we keep moving left until we find the correct position for our current element, which may involve swapping values to keep the order intact.

Think of filling a bottle with water. As you pour water in, you ensure that the amount in the bottle stays organized. If you splashed in more water (the new element), you rearrange it until everything settles into its proper level without spilling over.

In the worst case, you might have to put the element in the left-most position, and all k elements already there must be shifted right by 1. This leads to a time complexity of O(n^2).

This chunk discusses the time complexity of the Insertion Sort algorithm. The worst case situation occurs when we're inserting an element into the very beginning of the sorted section, causing all previous elements to shift right. This results in a quadratic time complexity, O(n^2), which means that as the number of elements increases, the time taken increases significantly.

Consider a slow-moving line at a grocery store checkout. If only one register is open, and a new customer enters, everyone in line must move back to accommodate them. The longer the line grows, the more time it takes for that new customer to be served, illustrating the inefficiency when the number of items increases.

So, we sort part of the array, and then we insert an element into that to grow it. We can think of the array as having a sorted and an unsorted portion.

This chunk explores the recursive implementation of Insertion Sort, distinguished by dividing the array into sorted and unsorted parts. The recursive approach sorts the array by continually taking the first unsorted element and inserting it into the sorted segment. Recursion continues until the array is fully sorted.

Imagine stacking books where one section is already sorted, and you're adding more books as you go. Each time you add a new book, you position it in the right place, making adjustments in a consistent manner until a complete set is organized.

Insertion sort usually behaves better than selection sort, and both of them are better than bubble sort. Insertion sort can achieve linear time when applied to an already sorted list.

In this chunk, the efficiency of different sorting algorithms is compared. Insertion Sort tends to perform better than Selection Sort and Bubble Sort. Notably, if the input is already sorted, Insertion Sort can run in linear time, making it exceptionally efficient for such cases.

Think of organizing a drawer full of already sorted items (like spices): if everything is in order, adding a new spice means just finding the right spot, rather than reorganizing everything else from scratch. The ease of insertion here highlights how Insertion Sort excels when data is partially organized.

--