Why does Insert sorts the best case of great complexity O (n)?

Question

Below is my insertion sort code:

void InsertionSort(vector<int> & ioList) { int n = ioList.size(); for (int i = 1 ; i < n ; ++i) { for (int j = 0 ; j <= i ; ++j) { //Shift elements if needed(insert at correct loc) if (ioList[j] > ioList[i]) { int temp = ioList[j]; ioList[j] = ioList[i]; ioList[i] = temp; } } } } 

The average complexity of the O (n ^ 2) algorithm.

From my understanding of the big O-notation, this happens because in this case we run two loops (external one-1 time and internal 1, 1,2, ... n-1 = n (n-1) / 2 times and therefore, the resulting asymptomatic complexity of the algorithm is O (n ^ 2).

Now I read that the best case is when the input array is already sorted. And the big complexity of the O algorithm is O (n) in that case. But I don’t understand how this is possible, how in both cases (the middle and the best case) we have to run loops the same number of times and compare the elements. The only thing you can avoid is moving items.

So the complexity calculation also includes a component of this replacement operation?

Answer 1

Yes, this is because your implementation is incorrect. The inner loop should count from i-1 to 0 , and it should end as soon as it finds the ioList[j] element, which is already smaller than ioList[i] .

It is because of this termination criterion that the algorithm executes in O (n) time at best:

If the input list is already sorted, the inner loop will immediately stop for any i , that is, the number of computational steps performed will be proportional to the amount of time during which the outer loop is executed, i.e. O (n).

Answer 2

Your implementation of insertion sort is bad.

In your inner loop, you should not scan all the way to i-1 , replacing each element more than ioList[i] . Instead, you should scan back from i-1 until you find the right place to insert a new element (that is, until you find an element that is less than or equal to the new element) and paste it there. If the input is already sorted, then the correct insertion point will always be found immediately, and therefore the inner loop does not execute i-1 times, it runs only once.

Your sort is also worse than sorting the insert on average, because you always perform i+1 operations for each iteration of the outer loop - some of these operating systems are just a match, and some are the result of a comparison, followed by a swap. Insertion sorting should be performed on average by half, as for random / average input, the correct insertion point is halfway through the initial sorted segment. Swaps can also be avoided, so each operation is a comparison plus a copy.