2
$\begingroup$

I want to know that whether which of the following algorithm can be parallelized?

Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort.

Those which can't be, please explain me briefly that how? Or please try to tell me in simple words that what is parallelism in sorting algorithms.

$\endgroup$
11
  • 2
    $\begingroup$ An algorithm can be parallelized if some of its steps can be done in parallel (possibly with minor modifications to the algorithm). If you work through the high-level steps of each algorithm, you should figure out where you can do this. $\endgroup$ Sep 14 '13 at 0:55
  • 1
    $\begingroup$ What have you tried? i.e what is your own thought about different algorithms, e.g radix sort can be parallelized or not? Why? Is not important if your answers are wrong, but we should see that you already tried to solve them yourself. $\endgroup$
    – user742
    Sep 14 '13 at 14:11
  • 3
    $\begingroup$ @Val I am care with many other members. We expect at least very few thoughs from OP. See meta discussion: meta.cs.stackexchange.com/questions/356/… $\endgroup$
    – user742
    Sep 15 '13 at 0:28
  • 1
    $\begingroup$ @Val You may not be aware of this, but on Computer Science it is customary to ask for display of effort. Case in point, this question asks essentially on a book worth of answers but does not show that even the most fundamental Google query has been made. $\endgroup$
    – Raphael
    Sep 16 '13 at 7:56
  • 1
    $\begingroup$ Since the question is impossibly broad, I'm closing. Please restrict yourself to a single algorithm at a time and do some research before you ask, and include your findings. (I know for a fact that for some of these algorithms, you will find something.) $\endgroup$
    – Raphael
    Sep 16 '13 at 7:57
0
$\begingroup$

Check this link. Parallelism can be achieved by using pipeline of processing units or using multiple processor link.

For comparison based sorting lets take an example of quick sort , in quick sort after we find the pivot then we can process two parts in parallel.

quicksort(A)
if |A| = 1 then return A
i := rand int(|A|)
p := A[i]
in parallel do 
 L := quicksort({a : a ∈ A | a < p})
 E := {a : a ∈ A | a = p}
 G := quicksort({a : a ∈ A | a > p})
return L ++ E ++ G

Another example we can take is of Radix sort which does not directly compare keys to determine ordering.The basic radix sort algorithm (whether serial or parallel) examines the keys to be sorted one “digit” position at a time, starting with the least significant digit in each key.For implementation in parallel see this tutorial Parallel In-Place Radix Sort

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.