tag:blogger.com,1999:blog-7359791525336117032.post5473871821929980318..comments2020-04-24T20:58:07.807-05:00Comments on Castles of Air: Big O Notation 2: SortingAnonymoushttp://www.blogger.com/profile/05324968314168283095noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-7359791525336117032.post-18273593863872951002009-04-22T13:33:00.000-05:002009-04-22T13:33:00.000-05:00For a nice demonstration of some different sorting...For a nice demonstration of some different sorting algorithms side by side and under different conditions, try the site http://www.sorting-algorithms.com/Kargonethnoreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-5797717759329277862009-03-11T22:36:00.000-05:002009-03-11T22:36:00.000-05:00Ah, I was afraid I might have been wrong, so I loo...<I>Ah, I was afraid I might have been wrong, so I looked it up in advance. <A HREF="http://perldoc.perl.org/sort.html" REL="nofollow">Here is what I was reading</A>:</I><BR/><BR/>Aye, but scroll down 3 paragraphs:<BR/><BR/><I>The default algorithm is mergesort, which will be stable even if you do not explicitly demand it. But the stability of the default sort is a side-effect that could change in later versions.</I><BR/><BR/>It's also covered in detail in <A HREF="http://search.cpan.org/~jhi/perl-5.8.0/pod/perldelta.pod#Performance_Enhancements" REL="nofollow">perldelta580</A>, as the core devs obviously had to take the time to verify and justify their decision.<BR/><BR/>Ok, <I>now</I> I admit to being pedantic :-)<BR/><BR/>Anyway, it's not really germane to the rest of your article, of which algorithmic complexity is indeed overlooked by far too many programmers, who all too often leave others holding the bag by not carefully considering their program design. Thanks for covering this issue, I hope you do a long series on it :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-8827400281312747992009-03-11T11:52:00.000-05:002009-03-11T11:52:00.000-05:00Am I ever going to use this professionally?" My a...<EM>Am I ever going to use this professionally?" My answer is: "You might. For one thing, you can use it to show off in job interviews."</EM><BR/><BR/>Sadly, this is the case. While people argue about what is and isn't computer science(engineering), understanding the basics of runtime complexity does seem to have gone by the wayside. I'm very disappointed when people interview for jobs and have absolutely no clue about the subject. <BR/><BR/>Even softball questions like: "When would you use an array/vector over a list? vice-versa?" are often unanswerable. Let alone any discussion of sorting...<BR/><BR/>All of that aside, I'm enjoying your posts!ahttps://www.blogger.com/profile/03202031495623868181noreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-82965816632918275262009-03-11T09:40:00.000-05:002009-03-11T09:40:00.000-05:00Ah, I was afraid I might have been wrong, so I loo...Ah, I was afraid I might have been wrong, so I looked it up in advance. <A HREF="http://perldoc.perl.org/sort.html" REL="nofollow">Here is what I was reading</A>:<BR/><BR/><I>In Perl versions 5.6 and earlier the quicksort algorithm was used to implement sort(), but in Perl 5.8 a mergesort algorithm was also made available, mainly to guarantee worst case O(N log N) behaviour: the worst case of quicksort is O(N**2). In Perl 5.8 and later, quicksort defends against quadratic behaviour by shuffling large arrays before sorting.</I><BR/><BR/>According to the page, you can choose a merge sort yourself if you desire, but the default behavior is a shuffle followed by a quicksort.<BR/><BR/>For the benefit of people who don't have this imprint in their memory banks, there's a good reason for shuffling an array before quicksorting it. Ordinarily quicksort is O(n log n) on a randomize array. However, if your array is already sorted beforehand, Quicksort winds up being O(n^2). Obviously this is not good, because if you accidentally sort something twice, it hurts your performance and you also get nothing out of it.Anonymoushttps://www.blogger.com/profile/05324968314168283095noreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-21022367724928245172009-03-11T09:12:00.000-05:002009-03-11T09:12:00.000-05:00Yay, I really like your new blog so far. I did no...Yay, I really like your new blog so far. I did notice one thing, though :-)<BR/><BR/><I>If you type "sort @mylist" in Perl, you are instructing Perl to perform a QuickSort in most cases.</I><BR/><BR/>Actually, since 5.8.0, Perl has switched its default sort algorithm to <A HREF="http://en.wikipedia.org/wiki/Merge_sort" REL="nofollow">Merge Sort</A>. I'm not pointing this out to be pedantic, but to highlight this alternative algorithm, as it actually gives slightly higher performance than the QuickSort for most use cases :-)<BR/><BR/>Otherwise, great stuff! Keep it up!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-11857453424785000092009-03-10T14:51:00.000-05:002009-03-10T14:51:00.000-05:00When I find a pack of cards lying around, I often ...<I>When I find a pack of cards lying around, I often find myself shuffling them, dealing out about 10-20, and operating a QuickSort on them.</I><BR/><BR/>Not trying to start a geek DSW or anything, but I once <A HREF="http://www.ooblick.com/lamp/#geek" REL="nofollow">wrote a Makefile</A> to help me with a craft project. Because make is basically a tool for doing topological sorting (if that's the right term).<BR/><BR/><I>QuickSort usually requires a time of O(n*log n), and you can't do much better than that.</I><BR/><BR/>I seem to remember seeing a proof of this, that started with the observation that <I>n</I> items can be shuffled <I>n!</I> ways, and your algorithm has to be able to deal with all of them. I don't remember how it goes from there, though.<BR/><BR/><I>some readers are asking "What's with all this theory? Am I ever going to use this professionally?"</I><BR/><BR/>If you write code for a living, then yes. I find that in many cases, it's easier to write a slow algorithm than a fast one. In the example above, selection sort is easier to write than QuickSort. When you're writing experimental code or a first draft of something, it's okay to write something inefficient quickly, than to spend too much time getting it right. But it's best to know that this is inefficient, so you can leave a note to yourself to fix it in the production release.<BR/><BR/>Likewise, if your code is running too slowly, it helps to figure out the speed of the algorithms you're using, in order to improve it intelligently: if 50% of the time is spent sorting using an O(n*log n) algorithm, there's not much you can do to improve that. If the other 50% of the code uses an O(n^3) algorithm where it could be using an O(n^2) one, you'll get a lot more bang for the buck.<BR/><BR/>In his book "Deep C Secrets", Peter van der Linden talks about a slowness bug in Sun's C compiler. The compiler used a hash table to keep track of identifiers in the program being compiled. Hash functions are notoriously hard to write, so the developer had put in a quick and dirty one that simply returned 1 (effectively turning the O(1) hash table into an O(n) linked list), along with a comment saying to write a real hash function later.arensbhttps://www.blogger.com/profile/15251547886605570242noreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-22698273078758263632009-03-10T13:36:00.000-05:002009-03-10T13:36:00.000-05:00Love your posts. I don't know much about programmi...Love your posts. I don't know much about programming (can handle some Basic) but I love science in general and computer science is not the exception.Anonymoushttps://www.blogger.com/profile/07982409667756307764noreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-27147041859660647112009-03-10T10:36:00.000-05:002009-03-10T10:36:00.000-05:00The Wikipedia page on QuickSort is actually really...The Wikipedia page on QuickSort is actually really good, although it is a bit long-winded, as tech pages on Wikipedia tend to be. If I've got some time to kill in later posts, I might do a whole post about QuickSort.Anonymoushttps://www.blogger.com/profile/05324968314168283095noreply@blogger.comtag:blogger.com,1999:blog-7359791525336117032.post-63463514525315059932009-03-10T09:37:00.000-05:002009-03-10T09:37:00.000-05:00Love the blog. Keep em coming, I am currently work...Love the blog. Keep em coming, I am currently working for a software development company and I have a degree in Physics which makes what you say perfectly logical but I am missing much of the programming methodology you speak of. Please write more and if you could when you use an example such as QuickSort can you include equivalent functionality in other languages where possible??<BR/><BR/>Thanks,<BR/>ThundergodAnonymousnoreply@blogger.com