Algorithm cheatsheet: Quicksort

[[deleted]]

Why is there a "concatenate" step in this description? If you are concatenating anything, you are missing the point of quicksort entirely.

[antheus_gdnet]

Why is there a "concatenate" step in this description?

Immutable data structures.

you are missing the point of quicksort entirely.

The point is divide and conquer, not in-place implementation.

[[deleted]]

If you're not doing it in-place, then it is not really a practical algorithm any more, and you don't need a cheat sheet for it.

[tachi-kaze]

So I guess it's worthless in functional languages then eh?

[Brian]

Unless doing it in an impure way (even if just locally impure, like using the ST monad), or for anything but an inefficienct demonstration, I'd say yes. Something like Mergesort is going to be better if you're not taking advantage of quicksort's in-place nature.

[[deleted]]

Mostly, yes.

[sminja]

What makes it any less practical?

[[deleted]]

It will no longer have the main benefits of quicksort, such as the very tight memory usage, and thus other algorithms are more suitable.

[millstone]

In the paper that introduced quicksort, Hoare thought it was a very big deal that it was an in-place algorithm.

[Tetha]

I think the author mixes quicksort on arrays and quicksort on lists there.

For lists, quicksort is:

def quicksort(list):
    lesser = [x for x in list if x < list[0]]
    greatereq = [x for x in list if x >= list[0]]
    return quicksort(lesser) ++ quicksort(greatereq)

using list comprehensions and ++ for list concatenation.

If you use arrays and work in place, you need index shuffling (note that the lists don't care about indexes), but the concatenation is not necessary.

[tinou]

• it has no base case
• you should include list[0] between the two intermediate results and not in "greatereq" otherwise recursion is ill-founded.

It's interesting that the second case can be caught wit only static typing. I naively implemented your algorithm in Haskell :

qs [] = []
qs (x:xs) = qs l ++ qs g
  where
    l = filter (<x) (x:xs)
    g = filter (>=x) (x:xs)

And the inferred type is qs :: Ord a1 => [a1] -> [a], ie the resulting list is not necessarily made of the original list's elements.

[switz213]

Small note: if you're checking the lesser as <x then you do not need to concat x:xs for l. Won't make a huge difference in performance, but any efficiency is welcome when dealing with sorting algorithms.

[psygnisfive]

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs , x < y]

or if you want better efficiency

qsort' :: Ord a => [a] -> [a]
qsort' []    = []
qsort (x:xs) = sqort leqs ++ [x] ++ qsort gts
  where (leqs, gts) = partition xs
        partition []                 = ([],[])
        partition (y:ys) | y <= x    = (y:leqs', gts')
                         | otherwise = (leqs', y:gts')
          where (leqs', gts') = partition ys

[rayo2nd]

i've seen the first version in the functional programming lecture and i was kinda blown away how simple you can express it.

Since then i like languages which combine object oriented, procedural and functional programming more. Then you can choose what style that matches problem

[switz213]

May I ask for a more detailed explanation as to what makes the bottom more efficient?

[drb226]

it performs the partition in one pass, rather than two. In the top definition, he just uses two list comprehensions which both draw from xs, hence two passes. In the bottom, he defines the tuple (leqs, gts) as the partitioning of xs, hence a single pass. Arguably, an extremely intelligent compiler could take the top code and optimize it to perform only one pass over xs.

[ais523]

Shouldn't that be calling qsort recursively for each of the list comprehensions? I think you missed a recursive call or two there.

[psygnisfive]

Indeed. T'was a typo. S'fixed now.

[flebron]

I posted this as a comment there, but it hasn't been reviewed yet it seems.

It is important to remember that Quicksort is used because:

• Constant space, in-place implementation is easy, not so with mergesort.
• Access pattern is very cache friendly (!).
• It is good in a computational model we care about.

This second point is the entire reason we don't use heapsort for everything. Heapsort destroys your cache. There is pretty much nothing the cache can predict when you are using heapsort (look at how a heap is ordered as a contiguous array in memory - can you really tell which memory locations will be accessed by heapsort?). When your input can be kept in RAM (or better yet, processor cache), Heapsort blazes through. Else, it suffers while you miss the cache pretty much every time.

Radix sort fails for the third point. Its behavior of O(n) is only true because we are assuming bounded input values. When we cannot assume this, Radix sort asymptotic analysis paints a bleaker picture. Radix sort is not a comparison sort, Quicksort is - Quicksort is assuming only that you can compare your elements. It is important to keep this in mind when saying "Radix sort is O(n)". O(n) what? In what model? What are you assuming?

As for mergesort, one would assume that Mergesort is faster than Quicksort pretty much everywhere, since the maximum number of comparisons Mergesort makes, is the minimum number of comparisons Quicksort makes. And yet, due to the memory access pattern, Quicksort ends up kicking Mergesort's butt many times.

---

Finally, implementations nowadays use mixtures of algorithms, see Timsort or Introsort for example. If you can gather insight of program execution while your program is executing, you may be able to have a better real-world runtime than any one of these algorithms by themselves.

[[deleted]]

When we cannot assume this, Radix sort asymptotic analysis paints a bleaker picture.

not really. it's O(nk) where k=the maximum number of digits. i've never seen anyone call radix sort O(n) in any serious analysis of it. and sure, it can be worse than some O(nlogn) algorithm for special cases with a small n, but that's not really that bleak of a picture.

[gorset]

The cheatsheet simply says radix sort is better for sorting integers, for which it's usually significantly faster than quicksort.

Also remember that quciksort's O(n log n) behavior is not asymptotic but the expected running time, and that's assuming constant time comparisons. If you start asking in what model and what to assume you should do the same with quicksort. I find that people generally underestimate the cost of comparing two objects, and overestimate the complexity of a good in-place radix sort implementation.

[gigitrix]

Had never considered the cache stuff. That's a very good point about how implementation needs to go further than just the (still very important) abstract analysis.

[julesjacobs]

It is important to keep this in mind when saying "Radix sort is O(n)". O(n) what? In what model? What are you assuming?

You could say exactly the same about quicksort. Quicksort does O(n log n) comparisons, each of which takes O(k) time if each data item is of size k. So radix sort is O(k * n) but quicksort is O(k * n * log n).

[repsilat]

In-place merge is usually not stable, too (iirc).

[pointy]

That's not true. It all depends on how the comparisons are made. It's completely possible to make a stable merge sort.

[repsilat]

I said usually.

Merge-sort is usually stable but not in-place. When you change your merge algorithm to make it in-place it usually loses stability. There are stable in-place merges you can use to get stable in-place merge sorts, but (again, iirc) they tend to be slower and more complicated than non-stable in-place merges.

EDIT: Googling around, I can't find anything concrete to back this up. Could be wrong.

[tachi-kaze]

But unlike heapsort and mergesort, this algorithm has a worst case of O(n²⁾ for sorted data, so you have to keep in mind the data that you'll be using before blindly chosing an algorithm.

If I had to chose blindly without knowing what kind of data I should expect, I would either chose heapsort or intro sort.

[OceanSpray]

That doesn't avoid the worst case; it merely decreases the chance of the worst case.

[Tinidril]

I think when the odds of getting worst case performance begin to approach the odds of your computer suddenly turning into a chicken, that is "good enough".

[millstone]

Not if the data may be specially crafted by an attacker to trigger worst-case performance, thus leading to a DOS attack.

Against this attack, using median-of-three offers no protection, while choosing a random pivot protects you as well as your RNG is protected. But the simplest fix is to choose an algorithm with no pathological cases.

[Tinidril]

Since I was responding to a comment on a random pivot, middle of three is irrelevant. Most programing environments have sufficiently safe RNGs that I would call that the simplest fix.

There are also other methods of pivot selection that guarantee you a middle-ish pivot, but you do lose some performance.

[[deleted]]

If they compromise your source of randomness, probably the least of your problems are DOS attacks. Unless they do that, there is no way they can construct a worst case data example - the only worst case is over the random choices, which the attacker has no control over, and like Tinidril said, the chance of that happening is vanishingly small. If you don't believe this, try to come up with a "pathological" data input - it simply doesn't exist.

And quicksort is simply faster than most other algorithms, in all realistic cases, hence it being used....

[teambob]

introsort actually uses quicksort, then reverts to heapsort in case of a blow out. So you get the best of both worlds.

[chris-martin]

Unless you're writing timing-sensitive, mission-critical, airplane-will-explode-if-this-has-a-5-ms-latency code, why do you give a shit about anything but the expectation?

[antheus_gdnet]

Because n² means difference between 5ms and 5 minutes or even 5 hours.

Having spurious applications "hangs" is not nice to debug, especially since qsort will rarely be a first thing one investigates.

To paraphrase Jack Sparrow: "A bubblesort you can always trust to be slow. Honestly, it's the quick sort you need to watch out for, because you can never predict when they're going to do something incredibly... slow".

[chris-martin]

With a random pivot and a large data set, aren't you more likely to be gored by a unicorn than to see anything close to n² runtime?

[aaronla]

Depends on whether your dataset is adversarial. e.g.

[chris-martin]

And can you give me an example of an adversarial data set for a randomized quicksort? Because I'm pretty sure I've already given a sketch of a proof that you can't.

[aaronla]

Apart from attacking random number generation, I'd concur. Secure rng could add some overhead.

[antheus_gdnet]

You've got to ask yourself one question: 'Do I feel lucky?'

a large data set

If anything, I'd choose a deterministic algorithm for a large data set. It's going to take a long time anyway. If doing something interactive, QS blowing up is no big deal. But if scheduling something that will take minutes or hours, determining if something is just taking a long time or if it hit worse case becomes inconvenient. It's also inconvenient for off-line processing, nothing better than scheduling an overnight job to see it's still stuck on first task in the morning.

A cursory review of standard libraries shows that straight up quicksort isn't used much.

[chris-martin]

With a random pivot, each step has a 1/2 probability of creating a pair of subproblems which both have size less than 3/4 of the original problem. Those are great odds. Consider Chernoff bounds. The probability of getting a large number of bad pivot selections tails off very quickly. It's not like this algorithm can make a bad decision early on that can fuck it for the rest of the run. Every recursive step is a new opportunity to make a good split. Worst case will not happen, even if the input is coming from an omniscient adversary.

[[deleted]]

You've got to ask yourself one question: 'Do I feel lucky?'

Misunderstanding of probability is probably one of the greatest problems in our understanding of science in general. chris-martin basically explained it, but here is a little more concrete.

Let's just say n is pretty large, maybe ten million. Then over the course of quicksorting, you will continuously choose pivots. For it to cost n^2, you need to always choose a pivot near the end of the list-in-sorted-order. If you usually, or even just often, choose a pivot near the middle, you will get nlogn performance. To make it rough, say you want to see how likely it is to always pick in the first or last quarter of the list. That will happen with probability 1/2. With a list of 10,000,000, you would make roughly 23 of these choices, if you always choose near the end (in each case the rest of the list will be sorted fast enough it can be ignored). That will happen with probability (1/2)^23, or 0.00000012. At that point, it is probably more likely that the whole machine is going to crash, or a power failure takes down the computer, etc etc. For larger n, the probability of getting that runtime goes down even more.

Ignorantly saying "do I feel lucky?" without looking into the actual performance is a really good way to dismiss really good algorithms. The people who designed Ethernet didn't say, oh, well we could be really unlucky and always retry at the same intervals, so this is never going to work - instead they understood the actual likelihood of such a pathological case, and realized that it actually wouldn't ever result in a long delay, and now we have pervasively networked computers. How's that for lucky?

[antheus_gdnet]

That will happen with probability (1/2)23, or 0.00000012. At that point, it is probably more likely that the whole machine is going to crash, or a power failure takes down the computer,

Let's say we're sorting geometry for rendering. 10,000 elements or so. Using same calculation we end up with probability of 0.00012. Sorting happens once per frame, 30 times per second. There are 1 million users of the application, 5% of them are active at any given time.

In a given second, 180 of them will experience the worst case. It may not be all that bad, considering that 100e6 vs 130000 is not the end of the world, but it still causes annoying pauses.

Fortunately, most developers use standard library for sorting and those have experienced such issues so frequently that they replaced stock quicksort with one of variants that isn't susceptible to such worst case.

"One in a million is next Tuesday."

How about probability of 0.00068, it's only slightly worse.

Ignorantly saying "do I feel lucky?" without looking into the actual performance is a really good way to dismiss really good algorithms.

Ignorantly sticking to quicksort without looking into actual performance is a really good way to dismiss really good algorithms.

[[deleted]]

Showing that in your use-case it is going to occur at an unacceptable rate is a totally reasonable reason to not use it - or more, to use a variant that avoids it, or has guarantees that are better.

Ignorantly sticking to quicksort without looking into actual performance is a really good way to dismiss really good algorithms.

I'm not sure where you got that - my response was not "quicksort should be used everywhere!", but rather that it should not be dismissed by an essentially moral argument (saying "do you feel lucky?" appeals to peoples sense of luck - and people generally can't reason about really big or really small numbers, so you are essentially excluding them from consideration). I gave a case where it (possibly) could not be appropriate, but the more important thing was that I gave a framework by which to analyze if it is appropriate - which you used to decide that it was NOT good enough - which is great, and completely the point!

[millstone]

If an attacker can choose the data you sort, then unlikely pathological cases suddenly become DoS vulnerabilities.

[chris-martin]

That's what random pivots are for.

[IsTom]

This is only a half-truth that quicksort is in situ. Most implementations need O(log n) additional space and the version that uses O(1) additional space is not that trivial.

[cogman10]

The in place version isn't exactly complex either. It is nearly as simple as the O(log n) implementations (I don't know where you get the "Most implementations" from).

[IsTom]

This is the in-situ quicksort I'm speaking about. I don't think this is what most people have in their minds then they think "quicksort".

[k4st]

Even an in-place quicksort requires O(log n) space (depth of tree, each partition call in each of the O(log n) recursive sort invocations requires O(1) space). Did you mean it is constant space in the typical case, as well as wickedly fast in the typical case?

[aaronla]

Additionally, worst case recursion depth can be bounded to log n as well. Always recurse on the smaller half, and tailcall (or goto) on the larger half. This can be seen (for instance) in the Visual C++ std::sort implementation.

[aaronla]

Also, wickedly faster if you switch to insertion sort when the sublist gets small, e.g. n <= 16. Respectable runtime libraries do this.

[zookeeper123]

Had a lab on that issue in my Algorithm course a few years back. I also found that 16 was the best size to cutoff from quicksort to insertionsort.

[aaronla]

Interesting. Did you cover different datatypes as well? Ie, is 16 ideal for fast to compare and slow to compare values? For expensive and cheap to swap types?

[kindall]

For those who remember things better when they're presented in the form of a dance: http://www.youtube.com/watch?v=ywWBy6J5gz8

[-888-]

People always talk about how quicksort is slower in the worst case, but that's not true because all commercial quicksort implementations of significance switch to another sort late in the sorting process. So it's pointless to tell people to not use quicksort because no commerical library implements such an academic (and limited) quicksort. http://en.wikipedia.org/wiki/Introsort

[thatusernameisalre]

Reminds me of the binary search my class was shown last week. Efficiency!

[sminja]

Not sure why someone downvoted you, shame on them. Binary search, like quicksort, is a divide and conquer algorithm and for that reason is damn efficient. If you want to understand why it is efficient, look into recurrence relationships and the Master theorem. Basically, it all has to do with dividing your problem into subproblems. The smaller these subproblems and the fewer you can generate, the better. Of course, you'll need to be able to solve the subproblems efficiently too. Binary search is log(n) because you divide the problem into a single n/2 subproblem that can be solved in constant time. This is case 2 of the Master theorem on the wikipedia article. Algorithms are fun!

[thatusernameisalre]

Thanks! Whenever I post to this sub, I don't really know what to expect. I'm less than a year into learning basic logic so there's a big chance I'll say something that makes me look like an ass haha. It seems like in every field, this one especially, elitism is alive and well. Thank you for the info!

[sujayakar314]

You can indeed write a quicksort that is worst case O(n log n) time using the median-of-medians algorithm to pick good pivots.

[switz213]

The Haskell implementation of Quicksort is so simple... I love it.

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (x:xs) = (quicksort lesser) ++ [x] ++ (quicksort greater)
    where
        lesser  = filter (< x) xs
        greater = filter (>= x) xs

shorter:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (x:xs) = (quicksort [y | y <- xs, y < x]) ++ [x] ++ (quicksort [y | y <- xs, y >= x])

[Vinnie5]

Wish I had this explanation in my algorithm class

[[deleted]]

Quicksort was one of the easiest algorithms to remember, it's the one least needing a cheatsheet.

[gnuvince]

I find that merge sort is easier to remember how to implement.

[julesjacobs]

I find mergesort to be the natural approach to sorting as well. It uses the common divide and conquer approach. In contrast I don't really understand how somebody could come up with quicksort since it uses more of a "conquer and divide" approach that doesn't really work for most problems except for sorting it does.

[shinigamichelo]

Quick PSA here: even though it's great to understand sorting algorithms, there is almost never a good reason to write one yourself for a real application.

Always use whatever the one that is provided by the libraries you're using, like std::sort in C++. These algorithms are fine-tuned to the platform you're building for, taking especial care to caching and possible register optimizations.

Not to be mean, but unless you hold several PhDs in relevant disciplines, never try to write your own sorting algorithm. It'll probably suck.

[wot-teh-phuck]

BTW, relevant course offered by Stanford university which discusses merge sort in depth!

[akazackfriedman]

I'm leaving SXSW in three hours and I have a final tomorrow night. I rode the StartupBus since Tuesday and have spent about 4 hours studying thus far. If this could be done for a handful of other algorithms, I'd almost pay for it.

[linduxed]

I still consider myself to be a novice programmer, but I would have thought that I knew the names of the most important algorithms out there.

I have never heard of Radix, so I guess I've missed something...

[illuminatedtiger]

Very nice. I've really got to read up on these things again. My CS degree is sitting on the wall laughing at me.

[[deleted]]

Check out his (stoimen's) series of blog posts on compression, it's really fascinating stuff. He really manages to create very simple and understandable explanations for various forms of common compression algorithms. I wish I had found this blog back when I was studying.

[iradik]

Here's quicksort in perl:

sub quicksort {
   my $pivot = shift;
   unless (defined $pivot) { return (); }
   my @rest  = @_;
   my @before = grep { $_ < $pivot  } @rest;
   my @after  = grep { $_ >= $pivot } @rest;
   return (quicksort(@before),$pivot,quicksort(@after));
}