Quicksort trubbles.

pobocks has asked for the wisdom of the Perl Monks concerning the following question:

Update: Fixed! Thanks ever so much. This teaches me why NOT to program at 4 O'Clock (Or without strict and warnings).

I've been trying to implement quicksort (As a teaching problem, not for production) in both Perl and Common Lisp. I think I know where I'm wrong with the Common Lisp one, but I'm not sure where I'm going wrong with the Perl one. It seems to pass identical (Or at least identically starting) lists to the later recursions (quicksort(@less) and its fellows.

Here's the code as is, printlines and all:

#!/usr/bin/perl

sub quicksorty{
    my @list = @_;
    my @copy = @list;
    my $length = @list;
    my @less, @equal, @greater, @answer;
    if ($length <= 1){
    return @list;
    }
    my $pivot = $list[0];
    print "My pivot is $pivot\n";
    foreach (@list){
        if ($_ < $pivot){
            push(@less, (shift @copy ));
        }
        if ($_ == $pivot){
            push(@equal, (shift @copy));
        }
        if ($_ > $pivot){
            push(@greater, (shift @copy));
        }
    }
    unshift(@answer, quicksorty(@less));
    unshift(@answer, @equals);
    unshift(@answer, quicksorty(@greater));
    return @answer;
}

quicksorty(5,3,1,6,4,9);
[download]

Comment on Quicksort trubbles. Download Code

Replies are listed 'Best First'.
Re: Quicksort trubbles. by apl (Monsignor) on Mar 18, 2008 at 19:38 UTC
You have two problems. Replace `my @less, @equal, @greater, @answer;` with `my @less; my @equal; my @greater; my @answer;` [download] Replace `unshift(@answer, @equals);` with `unshift(@answer, @equal);` That will result in a decreasing sort being returned. I suggest you religiously specify `use strict;`. The problems were trivial to fix because they were specifically reported.	[reply] [d/l] [select]
Re: Quicksort trubbles. by pc88mxer (Vicar) on Mar 18, 2008 at 19:49 UTC
First you should `use strict` and `use warnings`. That would tell you that you missed parens in this declaration: `my (@less, @equal, @greater, @answer);` [download] It would also inform you that you misspelled `@equal` in: `unshift(@answer, @equal); # was @equals` [download] Fixing those two problems and adding a print statement at the end yields: `My pivot is 5 My pivot is 3 My pivot is 6 answer: 9 6 5 4 3 1` [download] Btw, I don't know why you feel you have to use `(shift @copy)` in your pushes. You can achieve the same thing with the much simpler: `if ($_ < $pivot) { push(@less, $_); } if ($_ == $pivot) { push(@equal, $_); } # etc...` [download]	[reply] [d/l] [select]
Re: Quicksort trubbles. by jwkrahn (Abbot) on Mar 18, 2008 at 22:16 UTC
I can golf that down `:-)` `sub quicksorty { return @_ if @_ < 2; print "My pivot is $_[0]\n"; my ( @l, @e, @g ); push @{ ( \@e, \@g, \@l )[ $_ <=> $_[ 0 ] ] }, $_ for @_; quicksorty( @g ), @e, quicksorty( @l ); }` [download]	[reply] [d/l] [select]
Re: Quicksort trubbles. by ysth (Canon) on Mar 19, 2008 at 06:33 UTC
Isn't the (or at least a) point of quicksort that it is an inplace sort? Try implementing it with your recursive function being passed an arrayref and a beginning and ending index to sort. -- Online Fortune Cookie Search	[reply]