Selection sort implementation

[ahrnjic3]

Hello,

My college group and I, tried to modify this algorithm by using selection sort which takes first k elements. However the precision we get for indices is less than 99.9% and the test function fails. This has lead us to believe that using selection sort for a parallel knn algorithm isn't possible. So, our question is if you think that it is possible and if it is how would you implement it? We can send you code for our selection sort method if you need it.

Kind regards,
Amer

[ghost]

Hello Amer and sorry for the late answer.
I don't see why selection sort would not be possible.
The problem is that the distances computed using the CPU or using CUDA are slightly different.
My guess is that random points are too close to each other.
You can try to increase the distance between points or use a regular grid to make sure the distance is greater than the computation error.
I hope this will help.
Best,
Vincent

[ahrnjic3]

Hello Vincent,

It's me again. We we're able to implement the selection sort into the algorithm, but it proved to be much slower than your implementation with insertion sort. We tried some other ideas but they failed and now we are out of them. Since our college project requires us to achieve any kind of speedup over previous work, we were wondering if you have any ideas that we could try to implement to speed the algorithm up? (even if it's a small speedup)

All the best,
Amer

[ghost]

You need to think about what you are trying to achieve. You don't want to sort the n distances and only keep the k smallest ones, you want to reject quickly the n-k points that are not the smallest distances and sort the other k distances. That's why a regular sorting algorithm won't be as fast as my naive implementation I believe. I'm pretty sure that if you keep the same logic but replace the insertion sort with a fancier sort (e.g. merge sort), you'll get a speedup.