Printable View
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:
What I mean is, what is 'O' and what is 'N'? And what does the '!' mean when you have "N!"?Quote:
Originally Posted by Article
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:
which looks a bit suspicious.Quote:
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.
You might want to save your effort and instead criticize mine into becoming satisfactory. One half of my tutorial is completed: http://shobadobs.com/big_o.htmlQuote:
Originally Posted by Prelude
>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.
Found an error! "The heap data structure has two very simple rules. It's a complete binary search tree ..."
A heap is not a binary search tree.
>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.
Quote:
It's considered to be pretty good for a sorting algorithm.
>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. ;)
But O notation is pretty cool when you start to understand it. I have found being a !math person, that reading algorithm books sort of exclude people who are not in the know. If you do decide to write an article on O notation, perhaps you would consider taking it from a pretty basic level of understanding so that hobbyists can reap the benefits of understanding the more technical aspect of algorithm efficiency.Quote:
Originally Posted by Prelude
edit:: so much for actually reading the whole thread before I put my two cents worth in...
Actually, I think I'm just bored and wanted to say something :)