7

As they say, "true quicksort sorts in-place". So the standard short Haskell code for quicksort,

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

what algorithm/computational process is it describing, after all?

It surely isn't what Tony Hoare devised, lacking its most defining feature, the in-place partitioning algorithm.

(the answer might be well known, but not yet here on SO).

correction: this question is in fact a duplicate: the answer is known on SO after all: cf. Pseudo-quicksort time complexity .

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 3
    It is describing quicksort. – Thomas Feb 09 '13 at 10:01
  • There's no evidence in the article you linked to that Hoare feels it's not quicksort unless it's in-place. – AndrewC Feb 09 '13 at 10:26
  • @AndrewC yes, that article might not be the best choice to support my case. But, that's the WP. What I mean (and I saw it argued many times) is how it is described in the original paper - and there the partition algorithm is very specific, with swaps and the moving boundaries. According to that view, there is no such thing as quicksort for (immutable) linked lists. (for mutable ones we could make an array of cell addresses and swap the cells contents - (not in Haskell of course)). – Will Ness Feb 09 '13 at 10:32
  • 1
    related: [Pseudo-quicksort time complexity](http://stackoverflow.com/questions/11355621/pseudo-quicksort-time-complexity) – jfs Feb 09 '13 at 10:56
  • 1
    According the word description in [the wikipedia article that you've linked](http://en.wikipedia.org/wiki/Quicksort) the code is an implementation of quicksort algorithm. – jfs Feb 09 '13 at 10:59
  • cf. https://stackoverflow.com/questions/23318948/haskell-quicksort-efficiency – Will Ness Oct 09 '18 at 07:51

3 Answers3

12

It's quicksort for linked lists.

Yup, this is quicksort, just not in-place. It matches the high-level algorithm for quicksort whilst changing the low-level implementation to match the data structure of linked lists. That's why it's quicksort for linked lists.

I'd prefer to say "quicksort was originally developed to work in-place" than "true quicksort is done in-place". There are many variants of quicksort including picking pivots randomly to avoid worse-case behaviour etc.. This is a sensible, clear definition of quicksort for linked lists.

This definition exactly matches how we teach quicksort to 16 year-old maths students in the UK. (We're teaching algorithms, not programming.) In-place very much obscures the purpose and design, which is why we don't teach that detail, despite being a million miles from teaching functional programming or linked lists. (That doesn't change the fact that the pair-swapping trick in-place algorithm is best when you have destructive update arrays.)

There is a time penalty to this definition, since it traverses the list twice for the two sublists. It's certainly possible to rewrite this to partition rather than filter, but I assert that that's optimising rather than changing the fundamental algorithm here, quicksort.

AndrewC
  • 32,300
  • 7
  • 79
  • 115
  • Tony Hoare's quicksort is *defined* by its in-place partitioning algorithm. I've edited the question. – Will Ness Feb 09 '13 at 10:20
  • @WillNess And this one is _defined_ by it's use of filtering? I don't think so. – AndrewC Feb 09 '13 at 10:32
  • This one is defined by its creation of temporary lists through filtering. Otherwise you are taking a too high view of it, overlooking the essential details. Of course it is perfectly OK to do so, just not for the purposes of this question. :) IOW I do concentrate more on the operational details, here. If my phrasing was not clear, I apologies. – Will Ness Feb 09 '13 at 10:39
  • and even the re-writes which traverse the list once, - still they don't partition in-place, but by creating the interim lists. ... `partition` is still doing the same, operationally - it separates a list into two new ones. – Will Ness Feb 09 '13 at 10:40
  • I think if you had asked Tony Hoare "Can you do quicksort on a linked list?", he'd have said somethink along the lines of "Well.. updating in place would be too slow, but you could make new linked lists for the recursive application." – AndrewC Feb 09 '13 at 10:50
  • can you please explain what exactly to be in-place mean? if I take an array (not a dictionary), does it matter if a sorting algorithm is in-place or not? – Alan Coromano Jul 25 '13 at 14:19
  • 1
    @MariusKavansky In-place means without making a new copy of the list. It matters if you have a vast amount of data on a machine with a small amount of memory. – AndrewC Jul 25 '13 at 14:45
  • @AndrewC, I confused it with being stable. It's not stable by default, correct? – Alan Coromano Jul 25 '13 at 14:50
  • @MariusKavansky It _is_ stable in this version, because `filter` preserves ordering, and the pivot value `p` remains in front of any elements that followed it in the original list. – AndrewC Jul 25 '13 at 14:59
1

All in-place algorithms require some "ceremony" in Haskell, where mutable state is hidden behind a monad. The algorithm above is quick sort, just not in-place.

Landei
  • 54,104
  • 13
  • 100
  • 195
  • quicksort by Tony Hoare is specifically defined by its in-place partitioning algorithm. Sorry for not emphasizing it more, I've edited the question. – Will Ness Feb 09 '13 at 10:16
  • If you already know what you want to hear ("This is *not* quicksort as defined by Tony Hoare"), why do you ask? However, as you just can't write in-place algorithms using Haskell lists, your code is as close to the *idea* of quicksort as possible, given that choice of data structure. – Landei Feb 10 '13 at 19:46
  • 1
    I don't see a contradiction. The question asks, "it is *not* an X, but *what* is it?". AFAIK it is OK to ask a question on SO when you (think that you) know the answer already, to make it known on SO. I didn't expect the dispute really. – Will Ness Feb 10 '13 at 21:41
1

The intended answer (from here) is that this is "really a deforested tree sort". Turns out, it is also mentioned on haskellwiki.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 1
    If you take the trees out of a tree sort, surely you have less justification for using the name tree sort than if you take swapping out of a quicksort? By this logic you could call it deswappinged quicksort. – AndrewC Feb 24 '13 at 21:41
  • @AndrewC I really don't know what to do here, Andrew. Should I unaccept? The arguments from the reddit discussion are somehow appealing for me. But see, I think it's this way: we can treat types as tagged lists (coming from the Lisp angle). Tree is just a tag; what we really do when we create a tree is, *smaller ones* go on the left, and *bigger ones* go on the right branch. So when we partition into two groups, it's *essentially* the same as when we put them into the two branches of the tree - left and right. IOW tree is "isomorphic" to a triple. – Will Ness Feb 24 '13 at 21:47
  • @AndrewC but in the original algo partitioning is done differently, with swaps. At no step in the treesort are we considering putting smaller ones on the right, and then swapping them to the left - when we create the tree, empty at first, then when we insert elts one by one into it, each goes either to the left, or to the right. ... BTW the name deswappinged quicksort is very good actually, I think. Good to have you back btw. :) – Will Ness Feb 24 '13 at 21:53
  • Accept what _you_ think is the best answer, not what _I_ think is the nest answer! That's what it's for! – AndrewC Feb 24 '13 at 22:19
  • I like your _essentially the same_ argument, but I assert that the algorithm we're talking about is also _essentially the same_ (at the higher level reasoning) as quicksort, so it's OK to use quicksort in it's name. – AndrewC Feb 24 '13 at 22:21
  • I don't actually have a problem with calling it deforested tree sort because it has an appealing superficial irony and does work conceptually, but I do argue that it's not much closer to treesort than it is to array-swap quicksort. – AndrewC Feb 24 '13 at 22:23
  • I guess it's more of a POV thing, here. Ain't it all. – Will Ness Feb 25 '13 at 09:02