RandQS (+mathematica code)
RandQSLet’s talk about algorithms! I’m taking a randomized algorithms course next semester and having never taken regular algorithms, I figured I should do some self-study first. So, basically I’m working my way through chapters 1-5 of the Randomized Algorithms textbook. The book is actually pretty reasonable, even for someone who hasn’t taken algorithms before. Ok, now let’s talk about something cool: RandQS.
RandQS is short for Randomized Quick-Sort. It’s an efficient algorithm used to sort lists of numbers. This is important because, for computers, sorting isn’t necessarily an easy task. If you gave a computer a long list of numbers, it would have to compare every number versus every other number and do this recursively – i.e. look at all possible combinations. This is not very computationally easy!
So, we use randomized algorithms. RandQS works like this:
- Pick a random number from our list.
- Take all of the numbers bigger than our random number and make a list. Do the same with the numbers smaller. So you’ll have two new lists.
- Go back to step 1 with our two new lists. Do this as many times as we need to.
Why is this important? First, this algorithm runs faster than its non-randomized deterministic cousin! Secondly, it’s really easy to implement. This is huge for people who have to design algorithms for sorting enormous quantities of data – like the people who build the sorting engine for MySQL, for example.
Since I am Mathematica geek, below is the relevant bit of Mathematica code, for those of you coming from Google looking for it. Note that this algorithm only works with unique sets but could probably be easily modified to work with sets that have duplicates. You can download the whole notebook file down at the bottom.
SetSize = 100;
S = RandomInteger[{0, 100}, SetSize]
RandQS[sss_] := Module[{sOne, sTwo, y}, (
(* pick our random element *)
y = RandomChoice[sss];
(* build set larger and set smaller by doing comparisons*)
sOne = sTwo = List[];
If[# < y, AppendTo[sOne, #]] & /@ sss;
If[# > y, AppendTo[sTwo, #]] & /@ sss;
If[Length[sOne] > 1, sOne = RandQS[sOne]];
If[Length[sTwo] > 1, sTwo = RandQS[sTwo]];
Return[Flatten[Join[sOne, {y}, sTwo]]];
)];
RandQS[S]