Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

Quicksort problem

by JediMasterT (Sexton)
on Nov 22, 2011 at 05:25 UTC ( #939368=perlquestion: print w/replies, xml ) Need Help??
JediMasterT has asked for the wisdom of the Perl Monks concerning the following question:

I've just gotten back to perl after about a year, and I'm a little rusty, so bear with me

For some fun practice, I have trying to implement Quicksort. Here is the code:

@end = quicksort(3, 2, 6, 5, 4); foreach (@end) { print "$_ "; } print "\n"; sub quicksort { my $pivot=pop; my @less; my @great; foreach (@_) { if ($_<$pivot) { push @less, $_; } else { push @great, $_; } } return quicksort(@less), $pivot, quicksort(@great); }

However, when I run the sub (with any array), it loops infinity, until perl runs out of memory and shuts down. Help?

UPDATE: for all (if any) looking for an answer, I didn't have a return @_ if (@#_<1); in the first line of my sub, so I never had a terminating statement. Thank you for your time.


Replies are listed 'Best First'.
Re: Quicksort problem
by BrowserUk (Pope) on Nov 22, 2011 at 05:49 UTC

    If you add print "@_"; to the top of your sub, you'll see the problem.

    Even when @less, @great and $pivot are empty, you still recurse.

    Changing your first line to: my $pivot=pop // return; will allow the recursion to terminate.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      how does the // part work?

        See perlop. The // operator essentially is a special or operator where it is testing the left hand side for definedness. I am pretty sure this became available in perl 5.10 four years ago but you can check perlhist and perldelta if you want to be sure.

        Cheers - L~R

        If the left part is not defined, the right is returned, otherwise the left one is. See perlop.
Re: Quicksort problem
by ansh batra (Friar) on Nov 22, 2011 at 06:14 UTC
    @end = quicksort(3, 2, 6, 5, 4); foreach (@end) { print "$_ "; } print "\n"; sub quicksort { @arr=@_; if($#arr < 1) { return @arr; } my $pivot=pop(@arr); my @less; my @great; foreach (@arr) { # print "@_"; if ($_<$pivot) { push @less, $_; } else { push @great, $_; } } return quicksort(@less), $pivot, quicksort(@great); }
    $#arr returns the index of the last element of @arr.
    so if @arr contains 1 element then its index will be 0 i.e < 1
Re: Quicksort problem
by hbm (Hermit) on Nov 22, 2011 at 14:53 UTC

    Unrelated to your sort, you might like this:

    #foreach (@end) { # print "$_ "; #} #print "\n"; print "@end\n";

      Yeah, I've been programming in Java for school, so I forgot how the print function works. I found out today, and was wondering how long it would take for someone to point it out.

Re: Quicksort problem
by JediMasterT (Sexton) on Nov 22, 2011 at 13:41 UTC

    Woke up this morning and realized I didn't have a terminating return @_ if (@#_<1); Derp. Thanks for all the replies, though.

Re: Quicksort problem
by Khen1950fx (Canon) on Nov 22, 2011 at 09:44 UTC
    The lazy way:
    #!/usr/bin/perl -slw use strict; use warnings; use Tie::Quicksort::Lazy TRIVIAL => 2; my @end = qw/ 3 2 6 5 4 /; my @sorted_input = sort @end; tie my @sorted, 'Tie::Quicksort::Lazy', @end; while (@sorted) { my $this = shift @sorted; print $this; }
Re: Quicksort problem
by Marshall (Abbot) on Nov 22, 2011 at 08:50 UTC
    Perl sort() has been and continues to be vastly improved. Sometimes there is a tiny step backward, but usually there is a big step forward.

    I recommend that you use Perl sort() rather than trying to implement a my_sort() routine yourself.

    Update: I skipped Perl 5.8 and went straight from 5.6 to 5.10. I know that the worst case quicksort issue (already ordered) went away. But more happened than just that. The sorting got significantly faster. Probably a combination of algorithm and implementation changes? I have not investigated all of the details. I just know that it is a lot faster. The sort time got so much better that it has caused me to re-think many places where I used techniques like Schwartzian transform.

    As a learning exercise, I think one should be familiar with all the basic sorting algorithms. There is a lot to be learned from that and there is a reason why this is taught in every CS curriculum. I guess I just wound up with a very long winded way of saying: the Perl sort() function is no slouch!

      While this is usually true in Perl, learning how different sorts work, how to implement them yourself, bigOh analysis of them, and under what scenarios they should or should not be used have great value.

      When in college, we had two schools teaching "computer science" - the CS program under the sciences, and one of the business tracks under the school of business. The school of business basically taught the students to use the foo function of the language de jour to do action bar. I helped a few people in my circle of influence from the business school wow their instructors (How's that so fast?) and classes by teaching them some of those differences. I also took on some projects speeding up code submitted by other (Update: I was in CS, not Business) business students as projects for departments around campus.

      My point is that even if the language's sort is the best for the purpose, it does not hurt to learn other methods, nor is it bad to know why it is the best for the purpose. Trying to implement it oneself can also give insight as to why the language's sort is the better choice.


      Interestingly enough, up until 5.8, Perl used Quicksort for sort()

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://939368]
Approved by planetscape
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (8)
As of 2018-01-16 16:28 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (182 votes). Check out past polls.