PDA

View Full Version : It's that time again!

Prelude
11-10-2005, 03:35 PM
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 (http://www.eternallyconfuzzled.com/tuts/sorting.html) is the updated version. I rewrote most of the code and changed most of the text, so it's a pretty complete rewrite.

Arigato!

SlyMaelstrom
11-10-2005, 03:52 PM

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

nickname_changed
11-10-2005, 04:46 PM
Prelude, I'm not sure if it's too "low" for you, but could you actually explain what this:

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.

Prelude
11-10-2005, 05:16 PM
>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 (http://en.wikipedia.org/wiki/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.

Micko
11-16-2005, 03:04 AM
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

-=SoKrA=-
11-16-2005, 01:36 PM
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.

Rashakil Fol
11-16-2005, 02:39 PM
O is Big O notation (http://en.wikipedia.org/wiki/Big_o_notation). It makes it way easier to compare algorithms, but I haven't gotten around to writing a tutorial on it yet. ;)

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.html

Prelude
11-16-2005, 02:47 PM
>You might want to save your effort
Too late (http://www.eternallyconfuzzled.com/articles/bigo.html), 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?

-=SoKrA=-
11-16-2005, 02:57 PM
>>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.

Rashakil Fol
11-16-2005, 03:28 PM
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.

Prelude
11-16-2005, 04:14 PM
>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.

CornedBee
11-17-2005, 11:47 AM
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).

Prelude
11-17-2005, 02:29 PM
>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.

bithub
11-17-2005, 02:44 PM

It's considered to be pretty good for a sorting algorithm.

Prelude
11-17-2005, 03:00 PM
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. ;)

kermit
11-17-2005, 05:40 PM
>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 (http://en.wikipedia.org/wiki/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.

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.

edit:: so much for actually reading the whole thread before I put my two cents worth in...

CornedBee
11-17-2005, 06:43 PM
Actually, I think I'm just bored and wanted to say something :)