# Sorting list and changing same values to nearly the same

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?

• That's incompletely specified. If you have more identical numbers in your input than the delta value allows, what do you want to happen? Commented Oct 22, 2014 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). Commented Oct 22, 2014 at 11:42

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! Commented Oct 22, 2014 at 11:41