1

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?

  • 3
    That's incompletely specified. If you have more identical numbers in your input than the delta value allows, what do you want to happen? – Kilian Foth Oct 22 '14 at 10:32
  • That is true, to be honest I'm thinking about the problem. Maybe I'll reduce the problem by simply reducing the number of allowed items to maxAllowedValue/delta. In the end it won't matter much since it is a case so minor that it is practically impossible to happen in the application and if somebody really intentionally tried to fill the input with so many points it could pretty much only happen intentionally and not in practical usage (where same inputs can happen in practical usage). – mishan Oct 22 '14 at 11:42
2

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;
  • Thanks, this is perfect. Your solution literally gave me a big wide smile. Hats off to you and your code, sir/lady! – mishan Oct 22 '14 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.