sri ramanuja seva

Earlier we saw how to insert a value into an array (basically, shift elements to the right starting from the last element, and insert the value at the appropriate position). We also saw a simple algorithm for sorting an array, namely Selection Sort, where we basically keep selecting the minimum from the unsorted portion of the array and keep bringing to the start of that portion.)
Here, we shall look at another simple, common algorithm for sorting the elements in an array, known as Insertion Sort.
We keep inserting subsequent elements at appropriate positions in a growing sorted subarray. Hence, its named as Insertion Sort.

(In the following series of posts on Insertion Sort, we shall look at how insertion sort works to sort arrays, we’ll try to understand the algorithm more, and also analyse its running time, and look at its pseudo-code. Here’s Part 1 of the series.)

---

Let’s take this as our initial array:

A: 10   |   6    |    8    |    20    |    14    |    9 

The array contains 6 elements as shown above. Our task is to sort it in non-descending order. (Non-descending is the same as ascending order. It means that a subsequent element should not be smaller than a previous element. Equal value elements are allowed to be together in any order.)
Let’s assume that the array elements are indexed as A[1] through A[6].

• We build the sorted array element-by-element.
• Initially, we assume that the array contains just one element – just the 1st element (A[1]). There is nothing to sort. This is the initial pass.
• In the next pass (Pass 1), we consider A[2]. We call this as the key for this pass. (In our example, the key or A[2] is 6.)
  • The array under consideration now contains 2 elements – A[1] and A[2].
  • We compare the key with A[1], which is 10.
  • Key is smaller. So, we shift 10 to the right by one position, and we insert the key before it.
  • Hence, at the end of Pass 1, the 1st two elements of array A are in sorted order (as 6 and 10 )

Array A at the end of Pass 1: 
A: 6   |   10    |    8    |    20    |    14    |    9

• Pass 2: We take the 3rd element (A[3]), which is 8 as the key for this pass.
  • The 1st two elements (A[1] and A[2]) are already in sorted order.
  • Our task is to insert the key into its appropriate sorted position among A[1] and A[2].
  • Compare key with A[2]. Key (8) is smaller than A[2] (10). Hence, shift A[2] to the right by one position.
  • Now, compare key with A[1]. Key (8) is greater than A[1] (6). Hence, no need to shift further. Keep A[1] where it is, and insert key at A[2].
  • Hence, at the end of this pass, the 1st three elements of A are in sorted order ( 6 , 8 , 10).

Array A at the end of Pass 2: 
A: 6   |   8    |    10    |    20    |    14    |    9

• Pass 3: We take the 4th element (A[4]) as the key. A[4] is 20.
  • our task is to find the appropriate position for 20 in sorted subarray (A[1] through A[3]) and insert it there.
  • Compare 20 with A[3] (10). Key is greater. No need to do any shifting, or any more comparisons in this pass. Key is already in its appropriate position.

Array A at the end of Pass 3: 
A: 6   |   8    |    10    |    20    |    14    |    9

• Pass 4: We take the next element, A[5] (14) as the key. We compare backwards, shift greater elements, and insert 14 in its appropriate position in the sorted subarray to its left.
• Then, in Pass 5, the final pass, we take 9 as the key, and insert that too into its appropriate position in the sorted subarray to its left. Once that is done, our array is completely sorted, and we are done.
  

---

In the next post, you can see a nice visual representation of the example that we just saw.
Insertion Sort – Part 2.