12,226 views

1 Answer

Best answer
6 votes
6 votes

Insertion sort works just like how you arrange a pack of playing cards in your hand.
1.Start with an empty hand with a pack of cards(faced down) on a table.
2.Pick one card at a time from the table and insert it in the correct position in your hand.
3.To find the correct position of the card, compare it with each card in the hand from right to left.
(Notice that cards in the hand are already sorted)

Algorithmically : 
Insertion Sort(A)

  1.  for i = 2 to length(A) // Start with the 2nd element because the first element is trivially sorted
  2.    x=A[i]  // x is the element you want to insert in right place into the already sorted set of elements
  3.    j=i-1    // Last index of the already sorted elements because thats where you want to start comparing x
  4.    while j>0 and A[j]>x // Whenever there is an element greater than x
  5.         A[j+1]=A[j] // shift it to the right
  6.         j = j-1
  7.    end while
  8.    A[j+1]=x // The correct position to insert x
  9.  end for

Analyzing the time complexity :


Best case :
1. Outer for loop runs for (n-1) times
4. Inner while loop exits the loop in the very first comparison // Eg - Sorted set : 2 4 5 7, Element to insert : 9
1+1+1+...+(n-1) times =>  Ω(n)


 Average case :
1. Outer for loop runs for (n-1) times
4. On average the inner while loop runs for (n-2)/2 times // Eg - Sorted set : 2 4 10 12, Element to insert : 9
1/2+2/2+3/2+4/2+....(n-1)/2 = (1+2+3+...+(n-1))/2
                                        = ((n-1)*n)/4 => Θ(n2)

Worst case :
1. Outer for loop runs for (n-1) times
4. In worst case the inner while loop runs for (n-2) times // Eg - Sorted set : 10 11 12 13, Element to insert : 9
1+2+3+...+(n-1) = ((n-1)*n)/2 => O(n2)


Also, have a look at the formal model/framework for analyzing algorithms :
1. Instructions are executed sequentially
2. Instructions are simple, like addition,multiplication, comparison, assignment etc are assumed to take one time unit
3. Infinite memory

 

selected by

Related questions

0 votes
0 votes
1 answer
1
LavTheRawkstar asked Jan 12, 2017
806 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
2 votes
2 votes
2 answers
2
Vikrant Singh asked Jan 31, 2015
1,691 views
What is the worst case time complexity to find the gcd(m,n) using best algorithm known?A. O(log(min(m,n)))B, O(log(max(m,n)))
2 votes
2 votes
2 answers
4
Amar Vashishth asked Aug 2, 2015
2,385 views
int fun(int n) { int count=0; for (int i= n; i 0; i/=2) for(int j=0; j< i; j++) count+= 1; return count; }