tag:blogger.com,1999:blog-5907655605807122632.post6243247965289109566..comments2024-03-19T02:17:41.360-07:00Comments on Perl Adventures: How does sort actually work?Anonymoushttp://www.blogger.com/profile/14422352024976746995noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-5907655605807122632.post-26108520562275184022014-02-25T13:28:59.393-08:002014-02-25T13:28:59.393-08:00If it makes you feel better, everything you wrote ...If it makes you feel better, everything you wrote (including the "please correct me if I'm wrong" parts) is correct. I would like to focus on<br /><br />> According to the perl docs, the quicksort algorithm used was unstable<br />> because it can become quadratic. What????<br />><br />> A stable sort preserves the order of list elements that compare equal so<br />> maybe the quicksort algorithm kept sorting list items that were exactly the<br />> same as each other, which made the run time and complexity higher.<br /><br />(because of the "maybe").<br /><br />You are correct that a stable sorting algorithm maintains the relative positions of equivalent elements. Sometimes, people talk about "stable algorithms" in the sense that you don't have abysmal worst case performance. It so happens that merge sort is stable in both senses of the term, and quick sort isn't stable in either sense. Unfortunately, the documents aren't all that clear here.<br /><br />Quicksort's worst case performance comes from what could be called a bug in how the original implementation chooses the pivot. If there were a lot of equivalent elements being sorted, the performance fell apart. Unfortunately, many libraries exist with this performance bug.<br /><br />However, it *is* possible to pick the pivot in a way that will never cause running time to go quadratic: http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf .Max Lybberthttps://www.blogger.com/profile/13935322217857952629noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-45903625822404271312014-02-25T02:54:25.468-08:002014-02-25T02:54:25.468-08:00I completely agree with what you said about perl d...I completely agree with what you said about perl documentation and I'm glad that this blog helped you!Anonymoushttps://www.blogger.com/profile/14422352024976746995noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-35678862099468217752014-02-25T01:27:32.990-08:002014-02-25T01:27:32.990-08:00Thank you :-)Thank you :-)Anonymoushttps://www.blogger.com/profile/14422352024976746995noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-5221989338044313072014-02-24T18:00:30.194-08:002014-02-24T18:00:30.194-08:00'sort { $a cmp $b } @array' is exactly the...'sort { $a cmp $b } @array' is exactly the same as 'sort @array', it's also the the same as 'sort sub{ $a cmp $b } @array'.<br /><br />The code that is in the braces ('{ }') is ordinary Perl code, it could be any code, it could also be a subroutine name 'sub example { $a cmp $b } ... sort example @array'.<br /><br />For example if the array is a list of hexadecimal numbers 'sort { hex($a) <=> hex($b) } @array'.<br /><br />'<=>' returns -1 if the left value is lower numerically, 0 if the two values are equal, 1 if the right value is lower.<br /><br />'cmp' does the same thing but compares them by their codepoints.<br />A is before Z, but Z is before a. It is the same as 'ord($a) <=> ord($b)'.<br /><br />Also you can change the sort type using the <a href="http://perldoc.perl.org/sort.html" rel="nofollow">'sort'</a> pragma.<br /><br />A more efficient way to use sort if there is a sizeable overhead in the code block given to sort, is to use what is called a <a href="https://en.wikipedia.org/wiki/Schwartzian_transform" rel="nofollow">Schwartzian transform</a> ( known as decorate-sort-undecorate in Lisp ).Brad Gilberthttps://www.blogger.com/profile/16194386450942224029noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-79803034561045345422014-02-24T15:09:11.780-08:002014-02-24T15:09:11.780-08:00Joel, her blog is not about being a Perl expert, i...Joel, her blog is not about being a Perl expert, it's about readers getting a window into her journey of learning Perl. Her explanation made sense to me in a way that a lot of Perl documentation doesn't. Too much Perl documentation explains things by using terms that themselves need explaining. If you're not a computer expert before you start learning Perl, it can be daunting. I've learned about two different ways that Perl approaches sort today, and it was really helpful. I'm not going to be "writing Perl extended modules in C."Verbilahttps://www.blogger.com/profile/17192522257904225548noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-27643139240494334872014-02-24T12:28:42.367-08:002014-02-24T12:28:42.367-08:00You have to profile your code given the task you a...You have to profile your code given the task you are trying to tackle. When you say, "but I'm sure that these are a minority..." you are making a generalization, an unfounded one at that. The fact is that the choice of algorithm can lessen the problem space -- that is, you know that algorithm A *should* perform better than algorithm B -- but that is little more than a starting point. Some small unanticipated factor may skew your results and demand a switch in your algorithmic choice for the implementation. <br /><br />Perl 5 can be extended through XS modules so if you find that you are unhappy with the particular sorting algorithm (or anything else that is performing like crud) employed you can write your own in C and call it to your heart's content. Your blog post appears to omit that. Profiling should tell you when that needs to occur. It doesn't matter if you are talking about Perl, PHP, Scala, or whatever -- you are going to find yourself in the same boat here. The only place on this page that I find the word 'profile' is under your picture.<br /><br />Furthermore, your article should be classified under 'generic coverage of sorting algorithms' rather than Perl. Core Perl implemented a particular algorithm found a problem with that, and implemented a different one but properly indicated that in POD. The coverage of WHY the switch was made may be entirely too involved for a POD. <br /><br />My recommendation is that, if you insist that upon doing so, blogging about Perl is that you spend more time researching or asking questions of people in the Perl community that have a better understanding of it. Try PerlMonks.org.Joelhttps://www.blogger.com/profile/18009804240077182255noreply@blogger.comtag:blogger.com,1999:blog-5907655605807122632.post-12899126897386893132014-02-24T10:40:06.264-08:002014-02-24T10:40:06.264-08:00I'm quite enjoying your perl blog. Ive found t...I'm quite enjoying your perl blog. Ive found that many perl programmers are rather long in the tooth, and as such no longer cover some of the topics that you've touched on. Its quite refreshing!<br /><br />Cheers, pete / http://petermblair.comPetehttps://www.blogger.com/profile/12775555464891225263noreply@blogger.com