Sorting list and changing same values to nearly the same

Question

I have a list of doubles that need to be sorted and changed so that there are no two numbers that are the same (difference smaller then 0.05) and I need to do it fast. I don't care about preserving order for values that are the same.

What I'm doing right now is:

List<double> values;

bool sortfunction(double a, double b)
{
   return a < b;
}


.....
qSort(values.start, values.end, sortfunction);

for(int i = 0; i < values.count() - 1; i++)
{
   if(values[i] == values[i+1])
   {
      values[i+1] += 0.1;
   }
}

But the problem is with lists like { 0. ,0. ,0. ,5. ,6.3 }. The result being { 0. ,0.1 ,0. ,5. ,6.3 }. Can you think of something that does not require multiple passes of sorting?

Answer 1

Clearly this is just a sketch:

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

std::vector<double> values = {0.0, 0.0, 0.0, 0.0, 0.1, 0.3, 0.4, 5.0, 6.3, 6.3};

int main()
{
  std::sort(values.begin(), values.end());

  for (int i(0), sup(values.size()); i < sup; ++i)
    for (int j(i + 1); j < sup && std::abs(values[i] - values[j]) < 0.05; ++j)
      values[j] += 0.1;

  for (auto v : values)
    std::cout << v << '\n';
}

With minor adjustments it'll work also for lists:

std::list<double> values = { ... };

values.sort();

for (auto a(values.begin()), end(values.end()); a != end; ++a)
  for (auto b(std::next(a)); b != end && std::abs(*a - *b) < 0.05; ++b)
    *b += 0.1;