It's that time again!

This is a discussion on It's that time again! within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Time for you kind people the shred all of my hard work to confetti by pointing out where I've made ...

  1. #1
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796

    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!
    My best code is written with the delete key.

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,068
    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.
    Sent from my iPadŽ

  3. #3
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    Prelude, I'm not sure if it's too "low" for you, but could you actually explain what this:
    Quote 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.
    Last edited by nickname_changed; 11-10-2005 at 03:57 PM.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  6. #6
    Me -=SoKrA=-'s Avatar
    Join Date
    Oct 2002
    Location
    Europe
    Posts
    448
    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.
    SoKrA-BTS "Judge not the program I made, but the one I've yet to code"
    I say what I say, I mean what I mean.
    IDE: emacs + make + gcc and proud of it.

  7. #7
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by Prelude
    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.
    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

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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?
    My best code is written with the delete key.

  9. #9
    Me -=SoKrA=-'s Avatar
    Join Date
    Oct 2002
    Location
    Europe
    Posts
    448
    >>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.
    SoKrA-BTS "Judge not the program I made, but the one I've yet to code"
    I say what I say, I mean what I mean.
    IDE: emacs + make + gcc and proud of it.

  10. #10
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  14. #14
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    I think he is just refering to your comments in this thread.
    It's considered to be pretty good for a sorting algorithm.

  15. #15
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to get current time
    By tsubasa in forum C Programming
    Replies: 3
    Last Post: 05-01-2009, 02:03 AM
  2. Replies: 11
    Last Post: 03-29-2009, 12:27 PM
  3. Help with assignment!
    By RVDFan85 in forum C++ Programming
    Replies: 12
    Last Post: 12-02-2006, 11:46 PM
  4. calculating user time and time elapsed
    By Neildadon in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2003, 05:00 PM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 09:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21