Invisible <voi### [at] devnull> wrote:
> Insert-sort is an O(N^2) algorithm. It takes O(N) time to work out where 
> the next item needs to go, and it takes O(N) time to move all the data 
> down one slot in order to make room to insert the new item.

  Don't you mean that it moves the data one slot *up* (iow. towards the
end of the array)? (Or is this a question of different ways of visualizing
an array? To me "up" is towards the end of the array and "down" is towards
the beginning, perhaps because "up" means "higher", in other words, higher
memory addresses.)

  (And of course you could start the insertion sort from the end of the
array instead of from the beginning, in which case you would move elements
"down", ie. towards the beginning of the array...)

> And you have 
> to do this sequence of operations exactly N times. Hence, O(N^2).

  At least the worst case (and average) scenarios. The best-case scenario
for insertion sort is O(N).

> An obvious optimisation is to do a binary search over the array. Then 
> you can find the correct insert-point in O(log N) time. But still it'll 
> take you O(N) operations to shift everything down one slot to make room.

  If you remove the requirement that the sorting must happen in-place and
that no extra memory (as a function of the size of the array) cannot be
used, then there's an easy way of making insertion sort O(N log N).

  Curiously, this algorithm happens to be very easily expressable in C++
(by using its standard library). Suppose you have a std::vector<T> named
'v' which contains the elements to sort. You can do an "insertion sort"
like this:

    std::multiset<T> tmp(v.begin(), v.end());
    v.assign(tmp.begin(), tmp.end());

  The first line copies all the elements in 'v' into a balanced binary
tree, and the second line copies them back to 'v'. Now they are sorted,
and in O(N log N) time.

  The first line performs, technically speaking, an insertion sort in
O(N log N) (the idea is exactly the same as in insertion sort, but the
insertion of an element can be done in O(log N) time because it's a tree
and not an array).

  Of course this is quite inefficient compared to more traditional
in-place O(N log N) sorting algorithms, which is why this method is not
very practical.

-- 
                                                          - Warp

Post a reply to this message