I am having a hard time understanding why best case of insertion sort in o(n) ?
for (int i = 0; i < size; i++) { for (int j = i; j > 0; j--) { int k = j-1; if( a[j] < a[k]){ int temp = a[j]; a[j] = a[k]; a[k] = temp; } } }Lets consider an example initial array [1,2,3,4,5] size = 5
first loop will go from i = 0 to size - 1
and second loop will go from i to 1 but lets assume, inner for loop also goes from 0 to size - 1 in other words inner for loop also executes (n-1) times similar to outer for loop
I agree there will be no swaps but there will be Comparison's, & it will be exactly equal as unsorted array ?
then n-1 (outer loop) * n - 1(inner loop) = n^2 - n + 1 = O(n^2)
can any one explain me where i m wrong ?
6 Answers
At first, this does not seem to be a proper code for insertion sort. It seems that you are using bubble sort code in reverse manner.
In an insertion sort code you don't replace a small element with every large element that falls before it, rather we skim through all the large elements that fall before it and only when we are at the point where there are no elements left or there is no more large element, then we place the small element at that place and shift/move all other succeeding elements.
As a part for O(n) time:
Lets consider an array of five already sorted elements - arr[11,13,15,17,19]. We move from first position element to last position.
Step 1: Take element 11, as it is first element we keep it as it is.
Step 2: Take element 13, look for element that falls before it(that is element 11), as 13>11, therefore no further need for looking at elements that fall before 11.
Step 3: Take element 15, look for element that falls before it(that is element 13), as 15>13, therefore no further need for looking at elements that fall before 13.
Step 4: Take element 17, look for element that falls before it(that is element 15), as 17>15, therefore no further need for looking at elements that fall before 15.
Step 5: Take element 19, look for element that falls before it(that is element 17), as 19>17, therefore no further need for looking at elements that fall before 17.
As we see that for five already sorted elements we required only 5 comparisons, thus for 'n' sorted elements we require only O(n) comparisons.
I hope above example clarifies your doubt.
Your code always runs in O(n^2). You have to break the inner for loop at the time you have found the place where the element should be.
Consider the following implementation of insertion sort:
for (i=1; i<n; i++) { j=i; while ((j>0) && (s[j] < s[j-1])) { swap(&s[j],&s[j-1]); j = j-1; } }The best case for any sorting algorithm is when input is already in sorted order. Here in such scenario, the condition at while loop always returns false and hence it only iterates for the outer for loop, doing the job in linear time with O(n) time complexity.
Here's one way to implement insertion sort.
Take an input list and an initially-empty output list.
Iterate through the input list and place each item to its appropriate position on the output list. Find the appropriate position by walking through the output list, starting at the first element.
Now, if your input is already sorted, then the insertion point will always be at the beginning or end of the output list. The first possibility corresponds to the best-case scenario; the second corresponds to the worst-case scenario.
For example, my input data is: 4 3 2 1.
Then the output list builds as:
4
3 4
2 3 4
1 2 3 4Since looking at the first element takes only O(1), then the time complexity is in the size of the input, or O(N).
4Best case of insertion sort is O(n) when array is already sorted.
But your algorithm will still take O(n^2) for sorted case. So you should go inside second loop only if condition fails. This way in case of sorted list you will never go inside your inner loop.
Check below links :
1Change your method to have this break condition and you will get best case complexity as O(n).
void insertionSort0(List<Integer> list)
{ int loop=0; for(int i=1;i<list.size();i++) { int target=(Integer)list.get(i); int pos=0; for(int j=i-1;j>=0;j--) { loop++; if((Integer)list.get(j)>target) { list.set(j+1, (Integer)list.get(j)); pos=j; } else { break; } } list.set(pos, target); } System.out.println("loop in for insertion sort" +loop);
}
