Quicksort parallel

[kimiya_ab]

hello everybody

I want to use quicksort in parallel form for my project but I really don't want to use the NVIDIA sample for that matter because I have to give a full hour speech about how exactly every part of my code work and the NVIDIA sample is extremely general and hard to understand.
Does anyone have any idea? any simple form of code for this particular sorting ??
I would appreciate your help.

 

[Ken g6]

Welcome to AnandTech Forums!

First, is this for Cuda, OpenCL, or for CPU work?

Second, does it have to be Quicksort? Merge sort is almost as fast, and simpler IMHO. Edit: depending on how you parallel Quicksort, merge sort could wind up a lot slower - it has a linear final pass. But parallel Quicksort does seem insanely complicated that way.

 

[kimiya_ab]

Welcome to AnandTech Forums!

First, is this for Cuda, OpenCL, or for CPU work?

Second, does it have to be Quicksort? Merge sort is almost as fast, and simpler IMHO.

thank u so much,

yeah I should have mentioned that I need it in Cuda!
and for ur 2nd question, yea !!! it has to be quicksort

 

[Ken g6]

Well, a Google search turned up this PDF.

And also, if you can consider something other than Quicksort: https://en.wikipedia.org/wiki/Bitonic_sorter

 

[DaveSimmons]

>> I really don't want to use the NVIDIA sample for that matter because I have to give a full hour speech about how exactly every part of my code work and the NVIDIA sample is extremely general and hard to understand.

It sounds like you would learn a lot about CUDA by working through this example until you do fully understand it. If you plan to continue to use CUDA it might be worth the time.

Goal 1: Get an OK grade with lowest effort possible.
Goal 2: Learn as much as you can about the subject, and become a superior developer. Get an A as a side effect.

Pick one

 

[beginner99]

Goal 1: Get an OK grade with lowest effort possible.
Goal 2: Learn as much as you can about the subject, and become a superior developer. Get an A as a side effect.

Pick one

OP, I always picked 1 back than and kind of regret it a bit. So yeah, pick 2 please.

 

[kimiya_ab]

OP, I always picked 1 back than and kind of regret it a bit. So yeah, pick 2 please.

the problem is that the quicksort is not a great choice for learning!
and I just need its code bcuz I m forced to use it. that's why I think there is absolutely no point for learning the quicksort sample and I want a quick easy way out of it. I even figured out how merge sort sample works but when I asked my professor for changing my method to merge sort cuz it's better she said No.
trust me there no learning point for quicksort in Cuda if there were such thing I would never have ask for the solution !!

 

[kimiya_ab]

Well, a Google search turned up this PDF.

And also, if you can consider something other than Quicksort: https://en.wikipedia.org/wiki/Bitonic_sorter

trust me if I could have changed my sorting method I would have use merge sort or bitonic sort they work far better in Cuda.

 

[DaveSimmons]

So you don't think you will learn anything useful by studying the "hard to understand" parts of Nvidia's code until they are easy to understand?

I'm not working with CUDA and haven't looked at their code, so I'm not qualified to agree or disagree. But if those parts use techniques that would help you in other tasks then you might be wrong.

 

[Greyguy1948]

An alternative in Mergesort, Open Mp and cpp:
http://pastebin.com/iC5Fcjrg