Manually sorting vector<int> in C++

Question

I am currently looking into how Vectors work in C++. I have read and understand their functionality pretty well.

I'm looking at different ways of sorting a vector object with 10,000 ints, I've used the std::sort method, and a shell sort.

I noticed that a shell sort for a vector is slower than sorting a simple C style array. I learnt this was because "Fast element insertion or removal in the middle of the container is not supported" (http://www.cppreference.com/wiki/container/vector/start). So obviously a shell sort with lots of random accesses is going to be quite slow.

I was wondering in anyones experience what a better manual sorting method would be for a vector with 10,000 ints? This is for a learning exercise you see! :)

Answer 1

For all intents and purposes, vectors are arrays with added niceties. Random access is as fast as the C-style array. Removing/inserting elements in the middle of a vector is slow - but the same applies to C-style arrays, too. Shell sort should be as fast on vectors as it is on arrays. To me, it sounds like you're doing something unorthodox.

Quicksort or introsort (std::sort is one) should be the fastest comparison-based sorts available to you. Mergesort is slightly slower than quicksort, but it does not have quicksort's susceptibility to pathological cases. On average, all of those take O(n lg n) time (with quadratic worst-case for quicksort).

EDITED UPDATE

Code: C-array and Vector based shellsorts. With optimisations or without, sorting 1 million elements takes twice as long for vectors, for a reason unbeknown to me. Looks like STL is doing a lot of error-checking when you access a vector.

Answer 2

Try the quickselect or quicksort algorithms (very similar but depends on what you need). In any case, these are just relatively simple and popular algorithms - more importantly, in practice they are fast (although they do have bad worst cases).

Regards,
Dennis M.