Talk:Quicksort (C Plus Plus)

From LiteratePrograms
Jump to: navigation, search

[edit] Pivot choice

Needless to say, the pivot choice in this article is quite poor. I don't see a reason why we can't choose a pivot at (pseudo)random. This requires a random access iterator, but you wouldn't be using quicksort on linked lists anyway. Deco 12:42, 28 March 2006 (PST)

You are right. After some reading, I see that my choice of pivot was really bad. I have changed it to the median of first, middle and last element. I hope that choice is better, but I really do not know much about these things (just wrote the code, after reading about the algorithm in Wikipedia), so help from someone more knowledgable would be appreciated. Ahy1 13:32, 28 March 2006 (PST)
This isn't a terrible choice, but really a randomly chosen index would probably be better. When people do median of first/middle/last they usually also include a couple random indexes. It is pretty good if you want to avoid randomness though. Deco 03:14, 29 March 2006 (PST)
hijacker
hijacker
hijacker
hijacker