12.1.2. Insertion Process

So, let us continue with a discussion of sorting, and look at another simple sorting algorithm. And the example that we have in hand, is one way we are ask to sort a bunch of exam papers in descending order of marks. So, second strategy to sort this bunch of a exam papers would be the following...

This chunk introduces the concept of Insertion Sort as a simple sorting technique. Insertion Sort works by taking elements from an unsorted list and inserting them into their correct position in an already sorted list. The example of sorting exam papers demonstrates how sorting can be applied to real-life scenarios, emphasizing the need for sorting in varied applications.

Imagine sorting playing cards. When you take a new card, you look at your already organized hand and find where that new card fits in, sliding it into place—that’s exactly how Insertion Sort works!

So, at each point you pick up the top most paper in the unsorted stack, and you insert it into its correct position, in the sorted stack that you have building up...

This chunk explains the insertion process where you take the topmost element from the unsorted stack and find the correct position in the sorted stack for that element. It uses the progression of comparing the current element with previously sorted elements to insert it at the right place, ensuring the entire collection remains sorted after each insertion.

Think of this like organizing books on a shelf by height; each time you get a new book, you don't just set it on the shelf randomly. Instead, you measure it against the books already there and place it where it belongs to maintain order.

So, we start by building a sorted sequence with one element. This is called insertion sort...

This section details how Insertion Sort builds a sorted array incrementally. You start with the first element as a sorted list and progressively add each unsorted element into its appropriate position among the already sorted elements. This process is repeated until all elements are sorted.

Consider a small group of friends seated based on height. Whenever a new friend joins, they assess themselves against those already seated and take the spot that keeps everyone in order—shortest to tallest.

So, this is a very straight forward iterative implementation again. What will do is, we have an initial array a, and position 0 to n minus 1...

This chunk covers how to implement the Insertion Sort algorithm iteratively. It starts from the second element and proceeds to compare it with its predecessors to find its correct position, moving left while swapping as necessary. This continues for each element in the array.

Imagine a line of people passing a ball backward. Each person looks at the player behind them to find their spot in line and passes the ball when they find someone shorter; this is akin to how elements are examined and repositioned in Insertion Sort.

If you want to actually find the position where it must go, we can use binary search, but even if you find the position where it must go in logarithmic time...

This section analyzes the time complexity of Insertion Sort. While finding the insertion point can be optimized with searching techniques, the movement of elements to create space for insertion still costs linear time. Therefore, despite strategies to find positions more quickly, the overall complexity remains quadratic, particularly in worst-case scenarios.

Consider a crowded elevator. Even if you know exactly where you need to stand based on other passengers' heights (a quick way to identify your spot), you still have to navigate through the crowd, which slows down your progress.

So, once again as we saw for selection sort. There is a natural way to think of insertion sort as a recursive thing...

This chunk presents an alternative approach to understanding Insertion Sort via recursion. It explains how the sorting process can be broken down into smaller tasks, where each recursive call handles an element until the entire array is sorted. The recursive approach mirrors the iterative one at its core but expresses the sequence of operations differently.

Picture a chef assembling a complex dish; they focus on one ingredient at a time, perfecting each stage before adding the next one, similar to how the recursive function adds elements to the sorted list.

So, what we have seen is that, the two natural algorithms that we would typically applied when we do something manually; selection sort and insertion sort are both order n square...

This final chunk summarizes the performance comparison of Insertion Sort with other sorting algorithms. It highlights that although both Insertion Sort and Selection Sort have similar time complexities, Insertion Sort performs better in practice, particularly on sorted data, making it a preferable choice in many scenarios despite its quadratic nature.

Consider a file cabinet; if it’s already well-organized, adding new files is quick and easy. However, if everything is thrown in mixed up, it takes significantly longer to sift through and find the right position.

--