sri ramanuja seva

(In the previous post on Insertion Sort, we saw a nice graphic representation to illustrate its working on a sample array.)

Here’s the insertion sort algorithm summarised in simple words:

• In any pass, there is a sorted subarray on the left, and a key. The task is to insert the key into the appropriate position in that sorted subarray. (In order to do so, we make comparisons, and shift some elements to the right.)
• At the end of each pass, the sorted subarray grows by one element,
• Pass 1: Key is the 2nd element. And the sorted subarray consists of just the 1st element of the array.
• Final Pass: Key is the last element (A[n]), and sorted subarray contains (n-1) elements. When that key also gets inserted, the entire array gets sorted, and the algorithm terminates.
• How many passes are there in all? Answer: n-1.

Running time analysis of Insertion Sort

Total number of passes (for array having n elements) is n – 1.
In each pass:

• need to compare key with elements of sorted subarray
• And, insert key at appropriate position.
  

Best-case running time:

• Let’s assume the input array is already sorted.

For example: A -   10   |    14    |    25     |    27   |   50. 

• In each pass, we’ll select a key. We’ll compare key with last element of sorted subarray. Key is already in its appropriate position. No more comparisons, or shifting needed.
• For example, in Pass 2 for the above array:
  • key would be 25.
  • sorted subarray would be 10 , 14.
  • 25 > 14.
  • No need to do any more comparisons in this pass. And no need to do any shifting of elements.
• Similar is the case with other passes too.
• Running time:
  • O(1) [constant time] in each pass.
  • O(n) passes in all
  • Hence, O(n) is best-case running time.

Worst-case running time

Let’s assume that the array is reverse-sorted.

E.g. A :      50   |   34    |   22    |    18    |    5

• Total (n-1) passes as usual.
• In each pass, key will need to be inserted at appropriate position in sorted subarray.
• Let’s take Pass 2.
  • Key is 22.
  • Sorted subarray is 34, 50.
  • 22 < 50. Hence, shift 50 to the right.
  • 22 < 34. Hence, shift 34 to the right.
  • And insert 22 at the beginning of the array.
• Similarly, in each pass, the key would need to be inserted at the beginning of the array. All the elements of the sorted subarray in each pass will need to be compared and shifted. This holds true for every pass in our reverse-sorted input example.
• Total number of comparisons/shiftings that we do is something like: 1 + 2 + 3 + … + (n-1), which is O(n^2).
• Hence, worst-case running time is O(n^2).

Average-case running time is also O(n^2).

---

In the next post, we shall look at a few more details related to Insertion Sort, and look at its pseudo-code.