What sort should I use?

Question

I writing a program in C++, I gave a vector of 10 elements(always) and each elements have a value called position, which is an int. I want this vector to be always sorted, so as soon as I update it I sort it with std::sort for now. The thing is most of the time, like 99 percent of the time the vector is already totally sorted.

Should I use std::sort anyway ? or Is there a better way to do ?

ps: The update is: getting a a point from a point cloud, calculate in which element of the vector it belong to regarding some external factor and increasing the counter of the vector element designated. Depending of this counter I will add a new element to the vector and delete one of the old ones.

Possible duplicate of [When is each sorting algorithm used?](https://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used) — , Aug 01 '18 at 09:45
for a vector of 10 elements the performance should not be a concern, unless you have actually find it to be a bottleneck. — bolov, Aug 01 '18 at 09:45
You might consider `std::set` instead of `std::vector`. Sorting a vector after each update would be generally inefficient. — Daniel Langr, Aug 01 '18 at 09:47
@DanielLangr I don't think the overhead of `std::set` is justified for a 10 element container. — bolov, Aug 01 '18 at 09:47
Nobody can answer this properly unless we know what kind of data you're handling and how much you're going to be handling. If you're never touching more than 10 elements then `std::sort` is perfectly adequate. If you're going to be handling a lot of data then instead of sorting a vector, you'd probably be better off using a self-sorting data structure, like a self-balancing binary search tree. — Pharap, Aug 01 '18 at 09:48
Is the deletion you are talking about made in place? I mean, does the new element end up at the same place than the old element being deleted? — Rerito, Aug 01 '18 at 09:53
@bolov I don't think the *runtime* overhead of a `std::set` matters for a 10 element container, over the simplicity of *never having an unsorted container* — Caleth, Aug 01 '18 at 10:08

bolov · Answer 1 · 2018-08-01T10:22:36.393

First, if you always have 10 elements I would use std::array. This will enable some important optimizations because the size is known at compile time.

If you know the container is sorted you can use this information to find the new position of the element with std::lower_bound or std::upper_bound and then just move contiguous elements to make place for it if needed.

// replaces the element found at position replace_idx with new_value
// precondition: arr is sorted. 0 <= replace_idx < 10
// postcondition: arr is sorted
auto replace(std::array<E, 10>& arr, std::size_t replace_idx, const E& new_value)
{
    auto remove_it = arr.begin() + replace_idx;
    auto insert_it = std::lower_bound(arr.begin(), arr.end(), new_value);

    if (insert_it < remove_it)
        std::move(insert_it, remove_it, insert_it + 1);
    else if (insert_it > remove_it)
        std::move(remove_it + 1, insert_it + 1, remove_it);

    *insert_it = new_value;
}

Don't forget to profile, profile, profile!!

Disclaimer: not tested

Agree with profiling. For a size of 10 elements, there may not be any significant time savings between bubble sort, quick sort, merge sort or the other sorting algorithms. — Thomas Matthews, Aug 01 '18 at 14:28

score 0 · Answer 2 · answered Aug 01 '18 at 10:41

Typically, Insertion sort works pretty well for 'almost sorted arrays', specially if they're small in size.

As far as I know, C++ std::sort uses a group of sorting techniques including quick sort and insertion sort, which switches between them as the algorithm goes on. This means std::sort would -most of the time- actually give you the best performance for any size.

Another good solution 'd be to keep your array sorted all the time, and insert the number into the correct slot by scanning from the very beginning until you reach the suitable place. This works in linear time, as well as getting use of vector's insert() function.

What sort should I use?

2 Answers2