Using a genetic algorithm, I found this comparison list:
compareAndSwap(x[0],x[2]);
compareAndSwap(x[3],x[4]);
compareAndSwap(x[2],x[4]);
compareAndSwap(x[0],x[3]);
compareAndSwap(x[2],x[3]);
compareAndSwap(x[1],x[3]);
compareAndSwap(x[1],x[2]);
compareAndSwap(x[0],x[1]);
but I need to test it if it works for all cases. Also number of array elements(currently 5) can grow up to 100 in some situations. This would mean that number of cases to check against is growing fast like more than pow(2,100)
.
If I give an oppositely sorted array alone as a worst case, that doesn't check against any error about middle element x[2]
comparisons. For example, 5,4,3,2,1 is sorted by some function into 1,2,3,4,5, by
compareAndSwap(x[0],x[4]);
compareAndSwap(x[1],x[3]);
alone and this certainly doesn't sort many cases of 5-element arrays.
Tried random number generators for sample arrays but not sure if its acceptable:
std::random_device rd;
std::mt19937 rng(rd());
std::uniform_real_distribution<double> dist(0,1);
for(int k=0;k<500;k++)
{
std::vector<double> arraySorted;
for(int i=0;i<5;i++)
arraySorted.push_back(dist(rng));
//sortNetwork(arraySorted.data());
//if(!std::is_sorted(arraySorted.begin(),arraySorted.end()))
throw std::runtime_error("error");
}
even this can still miss some parts. Is there a fast way to test sorting algorithms?
How can I test if I find some way to sort a 1000-element array which means there are more than 2-to-the-power-of-1000 different cases?
Just some sample cases for 4 elements:
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
1 2 0 1
1 2 1 0
2 1 0 1
2 1 1 0
3 4 2 1
3 4 1 2
4 3 2 1
4 3 1 2
seems to have more than pow(2,n) cases.
Aucun commentaire:
Enregistrer un commentaire