Running Time For Insertion Sort

问题:

for (int p=1; p < a.size(); p++) {
    int tmp = a[p];
    for(j=p; j>0 && tmp < a[j-1]; j--) {
        a[j] = a[j-1];
    }
    a[j] = tmp;
}

I'm having trouble figuring out the worse case for Insertion sort. So, the array given is in descending order, and we want to sort it in ascending order.

The outer loop goes through the array. So, it runs (n times). O(n) int tmp=a[p] ---- This statement gets executed n times. O(n) The inner loop get executed (1+2+3+4+5+6+.... +n-1) times. O(n^2) a[j]= tmp-------- This statement get executed n times. O(n)

I'm not sure what to do after to find the running time for Insertion sort? Correct my work if you can. Thank you.

回答1:

Here's a two-line generic C++11 implementation of insertion sort

template< typename ForwardIterator, typename Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type> >
void insertion_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare())
{
        for (auto it = first; it != last; ++it) {
                auto const insertion = std::upper_bound(first, it, *it, cmp);
                std::rotate(insertion, it, std::next(it));
        }
}

The algorithm takes a range of elements (given by the two iterators first and last) and a comparison function (which is defaulted to the possibly builtin operator< for the elements pointed to).

The main loop (linear in the number of elements) keeps the subinterval [first, it) sorted, and repeatedly searches for an insertion point of where to put the next element. It's equivalent to your main loop. It does so with a binary search (logarithmic complexity). In your code you use a reverse linear search (wich has linear complexity but possibly better caching behavior).

After it has found the insertion point, it simply rotates the two ranges [insertion, it) and [it, it+1), which means swapping the current element into the insertion point. This rotation is linear in the number of elements that has been sorted so far. Since it is nested in the main loop, the overall complexity of insertion sort is quadratic, ie.e. O(N^2). Your code integrates the swapping and searching for an insertion point, but that does not change the complexity.

Note that when the input range is already sorted, the insertion point will always be equal to the element pointed to by it, and this means that the std::rotate does not have to swap anything at all. A sufficiently smart and optimizing compiler should be able to perform that optimization. If that is the case, insertion sort on a sorted range has linear complexity.

A similar 2-line approach to selection sort is given here.

回答2:

The outer loop executes n times.

Each run of the inner loop executes somewhere between 0 and p-1 times, where p varies from 0 to n. In the worse case, it will execute p-1 times. If p varies from 0 to n, then on average, p is n/2. So, the worst-case complexity for the inner loop is O(p-1) = O(n/2-1) = O(n).

Apart from the loops, the code is all O(1) (mostly importantly, the code inside the inner loop is), so it's only the loops that matter.

O(n) * O(n) = O(n^2).

QED.

This is roughly the analysis you yourself gave.