Thread: It's that time again!

Time for you kind people the shred all of my hard work to confetti by pointing out where I've made mistakes. My last sorting tutorial was written too quickly, and even though I'm still not sure if I took enough time writing the update, here is the updated version. I rewrote most of the code and changed most of the text, so it's a pretty complete rewrite.

Arigato!

I'm sorry I don't know a thing about this, so I can't really critique.

I'd be happy to read and learn a few things though.

Prelude, I'm not sure if it's too "low" for you, but could you actually explain what this:

Originally Posted by Article

The performance complexities you'll see primarily are O(N2), O(Nlog N), and O(N).

What I mean is, what is 'O' and what is 'N'? And what does the '!' mean when you have "N!"?

For those of us who haven't done this sort of thing in math it might help, though I don't know how hard it is to actually explain. I loved the introduction and I was really looking forward to learning about sorting properly, but unfortunately I had to stop reading as soon as I reached that section because the O/N stuff threw me.

>What I mean is, what is 'O' and what is 'N'? And what does the '!' mean when you have "N!"?
O is Big O notation. It makes it way easier to compare algorithms, but I haven't gotten around to writing a tutorial on it yet. N! is the mathematical notation for the factorial of N.

>For those of us who haven't done this sort of thing in math it might
>help, though I don't know how hard it is to actually explain.
Put simply, it's a way to determine the growth of an algorithm. For example, if you have an O(N^2) algorithm, the running time increases quadratically when N doubles. That's bad compared to O(N), where the running time grows in proportion to N. O(Nlog N), also given as O(N * log N) is inbetween O(N^2) and O(N). It's considered to be pretty good for a sorting algorithm. N is the number of items, by the way.

>but unfortunately I had to stop reading as soon as I reached that section because the O/N stuff threw me.
You don't have to know that stuff to get something out of the tutorial. I think I did a pretty good job of explaining which algorithms are good and which are bad without relying too much on O notation.

Nice work, Prelude.
After first reading, I like it, especially heap sort part
I didn't find anything "suspicious", but I'll read it throughly later.
I can say in general, that your tutorials are very good, especially for people who learned about subject earlier but as you said "didn't quite get it".
Congratulations!

- Micko

Hey, it's not related to this tut, but I found this on the random number tutorial:

However, these rules only apply to the formula when c is not zero. When c is not zero, the algorithm is typically called a mixed congruential generator.

which looks a bit suspicious.

>You might want to save your effort
Too late, I've already written an article for mortals who aren't math geeks.

>and instead criticize mine into becoming satisfactory
Can do, but it looks like yours can be a step up in sophistication from mine (and I'm not sure I could poke too many holes in it). I just give a quick and dirty "here's what this means to you" description.

>which looks a bit suspicious.
How so?

>>which looks a bit suspicious.
>How so?

Ah, nevermind. It threw me off a bit that you put Knuth's law in the middle there and then name it, I was expecting first a name and then an explanation (kind-of), but you first say the that there are rules and then you name it. Seeing those in that order confused me.

>A heap is not a binary search tree.
Now you'd think I would know what a binary search tree is, wouldn't you? I'm too used to writing about binary search trees, my fingers type it without any participation of my brain. Problem fixed, it now reads "It's a complete binary tree", but even that isn't entirely correct because you can have n-ary heaps... But I'll avoid going into those exceptions because then I would feel obliged to describe and implement them, and I have an update to the splay tree tutorial that's been sitting on my desk for weeks.

NlogN isn't "pretty good", it's "as good as generic sorting algorithms go". It's mathematically provable that sorting algorithms can't have a better complexity unless they make some assumptions about the data being sorted (e.g. properties of the sorted data, as in radix sorts, or partial pre-sortedness).

>NlogN isn't "pretty good", it's "as good as generic sorting algorithms go".
Can you quote where I said otherwise? I don't think I even attempted to step on that slippery slope.

>I think he is just refering to your comments in this thread.
Ooooh, I completely missed that. Thanks.

>NlogN isn't "pretty good", it's "as good as generic sorting algorithms go".
There's somewhat of a huge gaping difference between "a sorting algorithm" and "generic sorting algorithms". Methinks you're reading a little too much into my statement and then accidentally filling in the gaps with something you could correct.