Most efficient way to sort one element in a vector?

Question

I have a vector of elements which are sorted based some external value. It is a large container and looking up the sort-value is relatively expensive. At some point one element (only) needs to be re-sorted. What is the most efficient way to just re-sort that element? std::sort() the vector? erase-insert the element? compare the element to its immediate neighbours?

EDIT: to clarify, by erase-insert the element I mean something like this:

// erase the key and then insert-sort it
auto iter = std::find(keys.begin(), keys.end(), key);

keys.erase(iter);
SortedInsert(keys, index, <cmp>);

EDIT2: the container needs to be a vector for other performance reasons

Do you mean to insert one value into an existing sorted vector? — EvilTeach
The worst case is O(n) complexity (the one element gets moved from the end to the beginning) - you probably want another data structure (maybe std::set?) — milleniumbug
For the argument of sorted vector vs. set, an interesting article: asawicki.info/news_1352_the_beauty_of_sorted_arrays.html — Colin Pitrat
Since you ask how to do it fast, I assume you're going to do it often enough to make a difference. In this case you should work around this because it will be slow. For example, you can have additional non-sorted vector, which after it will be large enough, you'll reorganize it into your sorted vector - the large cost is amortized over many insertions. — milleniumbug

Colin Pitrat Colin Pitrat · Accepted Answer · 2016-03-20T14:50:57

If you want to insert an element directly at the right place in a sorted vector, you should use upper_bound to get an iterator and pass it to insert to place the element at the right place:

vec.insert(std::upper_bound(vec.begin(), vec.end(), item), item);

Note that upper_bound will be fast (O(log n)) but inserting can be slow (O(n)) because it will have to shift all the elements that are after the insertion point.

However, inserting at the end of the vector and calling std::sort is O(n log n) so it's worst, at least on big vectors !

vec.insert(item);
std::sort(vec.begin(), vec.end());

Another option could be to insert at the end of the vector and then shift with previous element until it's lower or equal. In this case, the insert is amortized O(1) and you have to do O(n) swaps.

I'm afraid there won't be an O(log n) solution as you could have with a list.

Most efficient way to sort one element in a vector?

4 Answers