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.
3
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.
2
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”.
1