CODEWITHSUNDEEP
algorithmsortinginsertion-sort
overexchange
overexchange

Reputation: 1

Insertion sort - Best/Average analysis

On referring Insertion sort lecture taught by Sedgewick,

I learnt that,

Proposition: To sort a randomly-ordered array with distinct keys, insertion sort uses ~(1/4 )N^2 compares and ~(1/4 )N^2 exchanges on average.

I also learnt that,

Best case - If the array is in ascending order, Insertion sort makes N-1 compares and zero exchanges

If I analyse the pseudo code,

int n = array.length;
for(int i=0; i < n; i++){
  for(int j=i; j>0; j--){
    if(less(a[j], a[j-1]))
      swap(array, j, j-1);
    else
      break; // Is N^2/4 due to break statement?
  }
}

Question:

So,

Due to break statement to avoid further comparisons, insertion sort performs (N^2)/4 comparisons in average case and N-1 comparisons, in best case.

Is my understanding correct?

Upvotes: 0

Views: 424

Answers (1)

user2736738
user2736738

Reputation: 30936

Ah a little more math is needed.

Did you Realize that number of swaps performed by insertion sort is exactly the number of inversions present in the input ?

Inversion: index pair (i,j) is an inversion if i<j but a[i]>a[j].

So I(i,j) = 1 if (i,j) is inversion
          = 0 if (i,J) is not an inversion

Now you have to get the expectation of this to get the average case
E[I]= Sum(E[I_{i,j}) = Sum over i and j such that i<j [(1/2)]= 1/2*nC2=n*(n-1)/2*1/2~n^2/4

Why E[I_(i,j)]=1/2?
    E[I_(i,j)]=P(I_(i,j)=1)*I_(i,j)+P(I_(i,j)=0)*I_(i,j)
              = 1/2*1+1/2*0
              = 1/2

How many indices are there with i 

1 2 3 4 .. n
For 1 there is 0 such indices
For 2 there is 1 such index [1]
For 3 there is 2 such index [1,2]
..
For n there is 1 such index [1,2,..n-1]
So total = 0+1+2..+n-1= n*(n-1)/2

Btw I guess you know this...but still.why 1+2+..n-1=n*(n-1)/2

Let the sum be S= 1+2+3+...+n-1
               S= n-1+n-2+....1
            -----------------------
              2*S= (n-1+1)+(n-2+2)...(1+n-1)
                 = n *n*n...n-1 times
                 = n*(n-1)
            So S = n*(n-1)/2

Upvotes: 1

Related Questions