Best algorithm to check whether a vector is sorted


Question

What would be the best way to check that a std::vector is sorted? Is there something faster than a loop checking that v[i]<=v[i+1]? Is it faster/cleaner with iterators? Or is it actually better to just call sort every time (though the "v is already sorted" case is quite common)?

We can safely assume the vector only contains PODs, usually floats and sometimes doubles and ints.

The size of the vector is non-trivial (usually a few thousands items) but not extreme (not gigabyte-sized).

  • in some instances we'll sort the vector immediately afterwards, however there are other instances where we don't (it's an error case of our algorithm).
  • we already use a flag "IsSorted" whenever possible.
1
18
10/11/2011 1:20:40 PM

Accepted Answer

Consider Multiple Cpu Cores

It depends on your platform and number of items in the vector. You'd have to benchmark to find what's best.

It's not possible to answer: Is there something faster than a loop checking that v[i]<=v[i+1] ?
With: No.

Because... computers now a days have multiple cpus/cores/hyperthreading. So, it may well be a lot quicker to exploit the parallism in the computer by spliting the work of checking to a number of threads, so each cpu can be checking a small range in parallel.

It's probably best to do this via a library function rather than implementing it yourself. New versions of libraries will exploit parallism. So, if you go for a std::sort you'll probably find when you build against newer implementations of STL, they'll do the operation in parallel for you without you having to worry about it. I don't know if there are readily available versions of STL that do this already, but it's worth sticking to the library functions so that when you upgrade to a version that does, this optimization is there for you without you needing to make any changes.

16
11/4/2008 4:57:26 PM

Is there something faster than a loop checking that v[i]<=v[i+1] ?

No.

If this is something you wish to check often, you might want to make a wrapper class that keeps a "sorted" flag which starts out False, is set to False whenever an item is added, and add a member function sort() that sets the flag to True after sorting.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon