Please review the Quicksort FAQ

Alright, I'm finally able to spend some significant time working on the FAQ again. Just "finished" the quicksort today. Please review it for accuracy, succinctness, ease of understanding, and make sure it has no dangling pointers.

(Quicksort is one of those obnoxious algorithms that really are relatively simple conceptually, but typically take a long time to wrap your head around. I hope to have explained it clearly enough to <i>understand it</i> sufficiently to begin coding it.)

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

Thank you for your time.
closed account (jwkNwA7f)
Looks great. Also, I didn't know this site had a FAQ.
Yup. Always has (http://www.cplusplus.com/info/faq/), but this will be the new FAQ.

Also, I suppose I should have posted links to previous posts on this topic,
where twicker asked What are the most F.A.Q. on this forum?

http://www.cplusplus.com/forum/lounge/60389/ (part 1)
http://www.cplusplus.com/forum/lounge/77387/ (part 2)

No one sees anything I obviously missed or got wrong?
closed account (jwkNwA7f)
Oh, yeah! Now, I remember seeing it there, sorry.
Current update: I think the counting sort is much more readable now.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/counting-sort/

(That animation took forever to create!)

Again, it is hard to copy edit your own work the day after you write it. Please check to make sure I didn't miss anything, or repeat myself too much. (The soonest I can objectively review it is next week.) Also please comment on how easy it is to follow the animation.

(I'm trying to make things as simple to follow as possible.)

Thank you again for your time.
Hi there,

As a less than mediocre hobbyist with no formal training in programming or algorithms, I think the article is very well written. Very concise, very well explained and it answered all the questions that came up in me while I was reading it.

If I were to comment anything else on it I might say that sometimes I found the wording to be slightly complicated at times. However, I think that depends on your target audience, so I'm not saying it's one way or the other. For instance, when I write stuff for true beginners, I sometimes intentionally leave out some details or specifics from the main text. To mitigate critics saying that this or that detail is important I will write a full explanation in an appendix or in a section marked "advanced". In this case for example, throwing optimization terms or attack vulnerabilities can be a bit daunting and over-complicate the matter to a beginner. I know I feel stupid when I read certain terms and I realize I never thought of their impact - so I imagine others might too.

Anyway, I should add that I don't write programming manuals, and many of the programming books I've read do it in the same way as you do, so it may be just me. I imagine it's a fine line between offering information to advanced users whilst keeping it understandable for beginners, hence my suggestion to clearly define your target group.

Just some thoughts I thought I'd share, but again: really well written and very concise.

All the best,
NwN
That is a very valid and welcome criticism.

The FAQ is supposed to be able to take someone who is moderately capable with C or C++ (beginner to intermediate), but who may be a complete beginner at algorithms (like sorting), and guide them through a sort sufficiently to make them an expert with that particular algorithm.

This involves a bit of a learning curve, but I have endeavored to keep things in a need-to-know kind of order, with more advanced stuff coming after the bare-minimum basics, and the ability to stop reading at any point.

Please let me know exactly where you found wording to be difficult to follow, and even a suggestion if you feel like it, and I will definitely take it into consideration.

BTW, you shouldn't feel stupid when you learn something new. If you knew it, you wouldn't need to learn it. Personally, I had never heard of some of these sorts before -- like the counting sort -- and all the examples I found online are, to be precise, difficult to follow. My goal is to present the algorithm as simply and correctly as possible, and build on that.

Thanks!


Oh, I've also been coding my own versions of these sorts (both for fun and to see what it takes). It has been fun. When I'm done I plan to make an Article showing what the STL can do for you when sorting. (It's pretty cool.) Most sorts take under 10 to 20 lines of code, with, with boilerplate, means about 30 lines of code for the really big ones. That includes advanced concerns like recursion limits and the like.
:O)
Hi Duoas,

It wasn't that I personally found the wording to be difficult, but I remember when I started with C++ that words like "stack frame", "parallelization", etc meant absolutely nothing to me. From what I gather around here it seems like these terms are also offered in more advanced courses, so beginners in a degree who get a sorting assignment in their intro-class might face the same.

Anyway I don't want to blow this up like it's a big issue, I just wanted to share that in my experience it is good to always consider your target audience. As I said, I really like these faqs.

I, for one, would be interested in you article on sorting and the STL, so please do keep us posted.

All the best,
NwN
You could mention that his aspirations to make this the default C++ library algorithm succeeded, and C++11 requires std::sort's worst-case complexity to be O(n log n).
(C++98/C++03 only required average case)
Thanks! How's that?


[edit]
Argh. Looking at radix sort now... I knew nothing about it before..

It's a messy one. Very nice for certain problems, like sorting strings and finding the longest common contiguous subsequence... but it is also one of those hybridized sorts...

and it's most unfortunate feature is that is it not a generalized sort; implementing it requires some pretty intimate knowledge about the data type being sorted.

This is going to take me a while to learn enough to write intelligently about it.



Foo.
Last edited on
Very nice job on the animation for selection sort! I immediately tried the optimization mentioned (cocktail sort) and it worked nicely.

I noted one (humorous) typo. Following the Stability header:
The sort can be made stable by a minor altercation:

We have to get in a fight with it?
Thank you for noticing that!

That is exactly why I need reviewers. (Because otherwise I'd miss a good fight with myself.)

:O)
Minor update
Replaced Wikipedia's animation with my own. (I'm trying to make the animations look like they belong together, to the C++ site. Instead of the block-ugly stuff from Wikipedia.)
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

Let me know if you think 2 or 4 go flying too quickly. (It is tough to balance the perception of time vs speed.)
I think the animations are just fine. These faq-entries are really interesting, thanks so much for your time and efforts Duoas.

All the best,
NwN
Topic archived. No new replies allowed.