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:
<code>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;
}
}
</code>
<code>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;
}
}
</code>
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?
2
Clearly this is just a sketch:
<code>#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';
}
</code>
<code>#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';
}
</code>
#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:
<code>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;
</code>
<code>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;
</code>
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;
1