Rename Quicksort!

[JamesCFraser]

My justification for this wanting to rename quicksort is quite simple. Whilst thinking about sorting lists quickly, and remembering a piece of code I'd written a little while ago, I thought, "Ah ha! I can reduce the time of my sort by pretending that I am working on a binary tree but have lost all of my right and left pointers!"

After briefly thinking about how to implement this (prior to this, I thought, "I've not heard of a binary sort, that would be a good name.") I realised that what I was thinking of was, in fact, quicksort.

So why isn't quicksort called binary sort?


If anyone else thinks it should be, then lets make a petition to have it renamed

[wing]

Quicksort should remain so named so that we can teach n00bs various sort algorithms and then go "btw, all that stuff we went over is useless damn near all the time. Check out this algorithm. It's called quicksort... Because it's quick."

It's name is a handy pneumonic device for remembering which sort algorithm to use. You can rename it when you can produce a faster general-purpose sort algorithm.

[EvanED]

And why do you feel "binary sort" is a fitting name? I think merge sort would be more fitting for that name.

[Rysto]

Because, as the OP explained(perhaps not so clearly), quicksort is just an in-place binary tree sort.

[btilly]

Because, as the OP explained(perhaps not so clearly), quicksort is just an in-place binary tree sort.

And sorting with a heapsort or a btree are both just as much binary tree sorts as quicksort. But the algorithms are very, very different.

Let's not rename quicksort.

[spelunker]

It's a silly name. We don't call the other algorithms by their speed. Bubble sort isn't called "horribly slow sort"; it's called bubble sort because that is the function by which it sorts.

Let's rename it.

[photosinensis]

The one thing I'll say for renaming quicksort is that it isn't always quick. After all, if you choose the worst case pivot, you're screwed. Any attempt to fix this problem by side-stepping it is only going to wind up being a pain in the ass.

I've got a way that I think might work to solve the problem of selecting optimal pivots, but I'm not entirely sure how well it will work in practice. I think that it runs in O(n) time with a coefficient of somewhere around 10.

[EvanED]

The one thing I'll say for renaming quicksort is that it isn't always quick. After all, if you choose the worst case pivot, you're screwed. Any attempt to fix this problem by side-stepping it is only going to wind up being a pain in the ass.

A median-of-three technique and a random technique are all pretty good, all very fast (at least if your comparisons are fast; if you're sorting strings or something like that, median-of-three is perhaps not a good choice), and all really easy to implement. Median-of-three will take care of the case of an already sorted (or anti-sorted) array, and random will improve all cases with a tiny probability of failure.

[OfficiallyHaphazard]

It is a silly name

I think it should be called: really-fast-and-surprisingly-cool-sort-(that-blows-away-your-face-with-its-quickness)

[segmentation fault]

why not just use radix sort and forget about all other sorts?

[btilly]

The one thing I'll say for renaming quicksort is that it isn't always quick. After all, if you choose the worst case pivot, you're screwed. Any attempt to fix this problem by side-stepping it is only going to wind up being a pain in the ass.

I've got a way that I think might work to solve the problem of selecting optimal pivots, but I'm not entirely sure how well it will work in practice. I think that it runs in O(n) time with a coefficient of somewhere around 10.

If your dataset is big enough that it has to live on disk, then quicksort is very, very painfully slow.

About optimal pivots, if it is any good then it is already well-understood. Sorting is the best studied area of computer science. (Not surprisingly, computers spend most of their computational time either sorting or hashing.)

[photosinensis]

If your dataset is big enough that it has to live on disk, then quicksort is very, very painfully slow.

Of course, if your data is on disk, any operations on it will be painfully slow. Best to avoid thrashing at all costs. Of course, that's another discussion and/or flamewar.

[btilly]

If your dataset is big enough that it has to live on disk, then quicksort is very, very painfully slow.

Of course, if your data is on disk, any operations on it will be painfully slow. Best to avoid thrashing at all costs. Of course, that's another discussion and/or flamewar.

It is only painfully slow if you use the wrong algorithms, and have the wrong expectations.

For example suppose you're trying to sort a billion items, each about 50 bytes, on commodity hardware. If it turns at 6000 rpm, then it turns 100 times per second, leading to random access times of about 1/200th of a second. Sorting this with a quicksort takes billions of random accesses to disk. (Many of the accesses can hit cache instead of disk, but billions still need to go to disk.) A billion accesses will take almost 58 days. Pain galore.

Now suppose the same disk has a sustained throughput of 70 MB/second. If we're using an unoptimized mergesort, we need to read each piece of data 30 times and write it 30 times. We have 50 GB of data. So we have 300 GB of data transfer. Which takes 71 minutes.

Slow? Sure. But given the size of the problem and the hardware available, a little over an hour is quite reasonable. However you see that quicksort does not run at reasonable speed by any reasonable measure.

Not about your other point, when you take code that is meant to run against RAM and run it against virtual memory on disk, the time to follow a pointer is now disk seek time. Looking at how slow that is, you can see why a computer seems to freeze when it starts "thrashing". The algorithms that are appropriate for normal use are a worst case scenario once data lives on disk. That doesn't mean that data can't be on disk while still having reasonable performance. Relational databases do that all of the time. But you need to access that data in appropriate patterns.

If you have never tried to understand how to use disk appropriately, but have encountered the worst case scenarios, then you can be pardoned for your excessively negative view of working with datasets that live on disk. However in the right circumstances it is quite reasonable to handle data on disk. (Though, of course, it would be nicer if you had enough RAM for it to all be there. But sometimes that is just not possible.)

[mlinsey]

why not just use radix sort and forget about all other sorts?

Maybe memory is an issue? Or we're sorting our own custom datatype and have to use a comparison-based sort?

[Rysto]

Because, as the OP explained(perhaps not so clearly), quicksort is just an in-place binary tree sort.

And sorting with a heapsort or a btree are both just as much binary tree sorts as quicksort. But the algorithms are very, very different.

Let's not rename quicksort.

Fine. Quicksort is just an in-place version of binary search tree sort. Are you happy, pedant?

[btilly]

Let's not rename quicksort.

Fine. Quicksort is just an in-place version of binary search tree sort. Are you happy, pedant?

Quicksort need not happen in-place. (Indeed the naive implementations never happen in-place.) Some other binary search tree sorts can happen in place. In fact an in-place version of heapsort requires only O(1) extra memory, while an in-place version of quicksort requires O(log(n)).

[Rysto]

Sorry, I messed up my terminology there. When I said "in-place" I meant "Doesn't need to allocate O(n) space as temporary storage for the list", which of course is not what in-place means.

In fact, an in-place quicksort would be more correctly called slowsort.

[btilly]

Sorry, I messed up my terminology there. When I said "in-place" I meant "Doesn't need to allocate O(n) space as temporary storage for the list", which of course is not what in-place means.

In fact, an in-place quicksort would be more correctly called slowsort.

Don't worry, we know what you meant by in-place.

Doesn't change the fact that a heapsort is another binary tree sort that can be done in-place.

[Rysto]

I already clarified that with binary search tree sort.

[adlaiff6]

Can we just call it godsort and be done with it?

[davean]

Can we just call it godsort and be done with it?

But it frequently isn't the best sort! Its only real commendation is it's low coefficients for common cases. When you need a reliably fast sort it is very slow comparatively and when you need parallelization it is atrocious and when you know anything more then a comparison operation for the data it sucks. More can be listed as fast as I could type for quite a while. It is a good general purpose sort on the standard types of architectures that we currently have when strong reliability of speed is not necessary and you know the bare minimum for sorting; it definitely isn't a truly superior sort.

[relmz32]

It's a silly name. We don't call the other algorithms by their speed. Bubble sort isn't called "horribly slow sort"; it's called bubble sort because that is the function by which it sorts.

While i don't think we should rename quicksort, I would totally say that "Horribly slow sort" is a far better name for bubble sort.
on a somewhat related note: In my first quarter of programming our C++ textbook got bubblesort and quicksort mixed up... it was like some kind of atrocity.

[adlaiff6]

Can we just call it godsort and be done with it?

But it frequently isn't the best sort! Its only real commendation is it's low coefficients for common cases. When you need a reliably fast sort it is very slow comparatively and when you need parallelization it is atrocious and when you know anything more then a comparison operation for the data it sucks. More can be listed as fast as I could type for quite a while. It is a good general purpose sort on the standard types of architectures that we currently have when strong reliability of speed is not necessary and you know the bare minimum for sorting; it definitely isn't a truly superior sort.

Oh yeah? Well <your favorite flavor of ice cream> sucks because it's not <hard/soft/chunky/smooth/cancer-curing> enough!

I just like it because it's beautiful. It's got pretty structure like mergesort, but is tail-recursive.

relmz32: Bubble sort is just as bad as insertion sort or selection sort, and is good for dynamic data structures (not to say insertion sort isn't, I suppose). Why do you say it's so slow?

[davean]

relmz32: Bubble sort is just as bad as insertion sort or selection sort, and is good for dynamic data structures (not to say insertion sort isn't, I suppose). Why do you say it's so slow?

Actually, bubble sort is MUCH worse then those generally. Bubble sort not only is O(n^2) it also uses about the maximum number of updates to the list possible. There is the reason it is considered the generically bad algorithm.

[zenten]

relmz32: Bubble sort is just as bad as insertion sort or selection sort, and is good for dynamic data structures (not to say insertion sort isn't, I suppose). Why do you say it's so slow?

Actually, bubble sort is MUCH worse then those generally. Bubble sort not only is O(n^2) it also uses about the maximum number of updates to the list possible. There is the reason it is considered the generically bad algorithm.

What's the best sorting algorithm when you only have 4 items, and don't know anything special about the order those items start in?

[wing]

There is the reason it is considered the generically bad algorithm.

You forgot bogosort.

[evilbeanfiend]

bogosort is only generically bad if you are considering the average or worst case time the best case is really good!

[Spartacus]

If you want to talk naming conventions, often algorithms are named after the individuals who first discovered them (Djikstra's, Shell Sort). So in honor of the man who developed quicksort, I think it should now be called Hoaresort. Unfortunately, attempts to correct Wikipedia in this regard have proved fruitless.

[phlip]

I could get behind "pivotsort" or "splitsort" or something... like the other common sorts, naming it after the major operation involved.

[Comic JK]

Quicksort is not at its best by itself; for best performance, it is usually combined with insertion sort in the base case of short lists.

Therefore it's hard to say that quicksort, purely defined, is the best sort.

[Philwelch]

There is the reason it is considered the generically bad algorithm.

You forgot bogosort.

bogo-sort: The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm).