Parallel Quicksort

Parallel Quicksort


Let’s apply scan in an interesting way, namely in parellelizing
the quicksort algorithm. And I know quicksort is your favorite
algorithm from computer science elementary school. First, let me remind you how to
do a quicksort sequentially. It’s all based on what I’ll
call a quicksort step. A quicksort step is a kind of dance
move for people like me who have two or more left feet. The first part of a quicksort
step is choosing a pivot element. Now, any element can work, but a good choice is to select
one uniformly at random. So for this 12-element array,
you might roll a 12-sided die and pick, I don’t know, this element. The next part of a quicksort
step is to partition the input around the pivot value. That means get all the elements that
are less than or equal to the pivot and put them on one side. And get all the elements that
are greater than the pivot and put them on the other side. By doing so,
you now have two subparts of the array that can be sorted completely
independently from one another. That ends the quick step. Now, since the two
halves are independent, you can spawn them as independent tasks. And you just keep repeating
the quick step until you’re done. Choose a pivot, partition and spawn. Here’s the algorithm more formally. First, it chooses a pivot at random. Then it partitions
the input around the pivot. Then it conquers these two halves. And finally, it glues these
two results back together. Quick and easy. Well, except for one detail. How do you do this
partition step in parallel?

About the Author: Michael Flood

1 Comment

  1. Its so incredibly thoughtless that I now have no idea how to get to the video following this. The videos don't even have any form of numbering!!

Leave a Reply

Your email address will not be published. Required fields are marked *