Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
for ( i = 1 ; i <= N ; i++ )
{
  for ( j = 0 ; j < i ; j++ )
  {
    if ( arr[j] > arr[i] )
    {
      temp = arr[j] ;
      arr[j] = arr[i] ;

      for ( k = i ; k > j ; k-- )
        arr[k] = arr[k - 1] ;

      arr[k + 1] = temp ;
    }
  }
}

Source: http://programminggeeks.com/c-code-for-insertion-sort/

If not, can it really be called insertion sort? This version of sort is there in a book from reputed author originally.

share|improve this question
    
Looks like O(3N + 7) to me as a first order approximation. I would thus say it has O(n) complexity ignoring the constant term. –  Mushy Apr 4 '13 at 11:23
6  
no it has at least O(n^2) because you never exit the inner loop prematurely –  ratchet freak Apr 4 '13 at 11:24
    
Can you share how best case(nearly sorted array) has 3N+5 comparisons? It looks like there will be approximately 1+2+3+4+...+N = N(N+1)/2 = (N^2+N)/2 comparisons which is O(N^2) –  amitamb Apr 4 '13 at 11:31

2 Answers 2

up vote 4 down vote accepted

The best case occurs when the if statement never gets entered. Then we just have to count the number of times we evaluate the condition of the if statement to determine that we don't want to do it.

The outer loop ranges i from 1 to N and the inner ranges j from 0 to i. Let's count the number of times we check that if-condition:

At i = 1  we look at j 1 times  (at j = 0)
At i = 2  we look at j 2 times  (at j = 0, 1)
At i = 3  we look at j 3 times  (at j - 0, 1, 2)
At i = 4  we look at j 4 times  (at j - 0, 1, 2, 3)
At i = 5  we look at j 5 times

At i = N-1  we look at j N times   (at j - 0, 1, 2, ... N-1)

This is the classic 1+2+3+4+....+N arithmetic series known to be O(N^2).

It is not insertion sort. Real insertion sort is O(N) in the best case.

I don't know what this algorithm is.

share|improve this answer
    
This does look like an insertion sort. It's just missing break inside that if statement, and then it would have O(N) complexity for arrays that are already sorted in reversed order. –  Piotr Kalinowski Apr 4 '13 at 14:55
    
You're right: it acts like insertion sort (though unusual in the j loop), but with a good deal of redundant checking. But there is really no reason to structure the algorithm with three nested loops. Two loops certainly suffice and the algorithm can be written very cleanly with just two. There do exist sorting algorithms with extra and useless computations, such as StupidSort, StoogeSort, BozoSort, BogoSort, etc. that do silly things. This algorithm I'm sure wasn't intended to be a purposely inefficient like the ones I just mentioned, but I thought it might nevertheless be named.... –  Ray Toal Apr 5 '13 at 4:41

Assuming it's already sorted, that if statement never gets entered. So you have two loops through everything and it'll execute in n^2 time.

But that's not "Big-O". Big-O cares about the worst time, not the best. I believe this algorithm is O(n^3). The inner loops only execute n/2 and ... I think n/3, but all that division gets thrown away when talking about Big-O.

It's been awhile but I think the best case scenario is called "big omega".

share|improve this answer
1  
Lower bounds (best case) is Big Omega, Upper bounds is Big O, approximate is Tilde and the growth rate is Big Theta. If I remember correctly. –  Jeroen Vannevel Apr 4 '13 at 14:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.