CODEWITHSUNDEEP
c++sorting
KaiserJohaan
KaiserJohaan

Reputation: 9240

Sorting one element in a sorted container

I have a vector of sorted objects. At some point one of the objects gets updated and that element (only) has to be sorted again.

What is the best approach? std::sort() on the whole container (if the container is already sorted, is it faster?) or erase() the object and insert() it where it should be?

EDIT: in this case I have to use a vector container

Upvotes: 2

Views: 1184

Answers (3)

Jarod42
Jarod42

Reputation: 217275

  • std::sort has a complexity of O(n log n).
  • removal and insertion has a complexity of O(n).
  • rotation has a complexity of O(log n) + O(length_of_rotation).

You can use std::lower_bound to find the new place and std::rotate to fix order:

void update(std::vector<int>& v, std::vector<int>::iterator old_it, int new_value)
{
    if (old_it == v.end()) {
        return;   
    }
    auto it = std::lower_bound(v.begin(), v.end(), new_value);
    *old_it = new_value;

    if (old_it < it) {
        std::rotate(old_it, old_it + 1, it);
    } else if (it < old_it) {
        std::rotate(it, old_it, old_it + 1);
    }
}

Demo

The advantage of std::rotate vs remove/insertion is the number of copy/move: if you have to swap only the 2 first elements, std::rotate does only the swap, whereas remove shift all elements, and insert shift again the element in the other side.

Upvotes: 3

Escualo
Escualo

Reputation: 42082

In theory, you should use a combination of std::lower_bound and std::insert, as shown in the example below:

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
void insert(T value, std::vector<T>& data) {
  auto it = std::lower_bound(data.begin(), data.end(), value);
  data.insert(it, value);
}

template<typename C>
void show(const C& data) {
  for(const auto & item : data) {
    std::cout << item << " ";
  }
  std::cout << "\n";
}

int main() {

  std::vector<int> data { 1, 2, 4, 5, 7, 9 };
  show(data);
  insert(3, data);
  show(data);
  insert(6, data);
  show(data);
}

Output:

$ g++ example.cpp -std=c++14
./a.out
1 2 4 5 7 9
1 2 3 4 5 7 9
1 2 3 4 5 6 7 9

std::lower_bound(beg, end, val) will find the iterator pointing to the first element in the range [beg, end) that is not less than (i.e. greater or equal to) value (cf. cppreference); it only works for sorted containers. Its complexity is logarithmic in std::distance(beg, end).

std::vector<T>::insert(it, value) will insert value before it.

In practice (for a relatively small number of elements), you may be better off using linear search up to the point of insertion and then std::insert. In other words: linear search is O(N), and std::lower_bound is O(log N), but linear search is faster (due to cache effects) for vectors with about 10-50 elements (your mileage may vary).

Upvotes: 5

Serge Ballesta
Serge Ballesta

Reputation: 148900

If the vector is already sorted, you can easily find the new place of the updated value by dichotomy (compare with value at size+2 and iterate ...). Then you shift all elements between old and new place.

This is a rather optimised way since the shift between old and new place is a condensed operation combining a std::erase and std::insert, but it will be more tedious to write and test...

Upvotes: 1

Related Questions