Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

quicksort implementation

by ram (Initiate)
on Oct 05, 2011 at 11:20 UTC ( #929763=perlquestion: print w/ replies, xml ) Need Help??
ram has asked for the wisdom of the Perl Monks concerning the following question:

Hello All Here is an attempt to implement quicksort, this is a failed attempt with %ha is tried to store index of the element which after comaparision will be at the rite index can somebody guide on where it is going wrong thanks in advance
use strict; use warnings; my $list = [ '1','5','2','3','4' ]; my $len = @$list; my @temp = @$list; my @ref = @$list; my $pivot = pop @$list; my @temp1 = $pivot; my %ha = ; while ($len-1){ foreach my $ele (@temp){ next if ($ele eq $pivot); if ($ele gt $pivot) { push @temp1,$ele; } else{ unshift @temp1,$ele; } } print "\n @temp1 \n"; $pivot = pop @$list; print "$pivot \n"; @temp = @temp1; my $i=0; foreach my $ele(@ref){ if ($ele eq $pivot){ $ha{$i}="$ele"; print $ha{$i}; } $i++ } @temp1 =(); @temp1 = $pivot; --$len; } print keys %ha;

Comment on quicksort implementation
Download Code
Re: quicksort implementation
by Anonymous Monk on Oct 05, 2011 at 11:38 UTC

    Well, aside from not being a subroutine one can call and test, it doesn't compile :)

    Also, purpose of %ha isn't clear

    Speedy Gonzales
        So here is Mi6 and Mip
        #!/usr/bin/perl -- use strict; use warnings; Main( @ARGV ); exit( 0 ); sub Main { Mi6(); print '#'x 33, "\n"; Mip(); } sub Mi6 { my $list = [ 1, 5, 2, 3, 4 ]; DD( $list ); DD( [ p6quicksort(@$list) ] ); $list = [ 3,2,4,5,1 ]; DD( $list ); DD( [ p6quicksort(@$list) ] ); } sub Mip { my $list = [ 1, 5, 2, 3, 4 ]; DD( $list ); DD( [ IPquicksort(@$list) ] ); $list = [ 3,2,4,5,1 ]; DD( $list ); DD( [ IPquicksort(@$list) ] ); } sub IPquicksort { my( @array ) = @_; IPquicksortREF( \@array, 0, $#array ); return @array; } sub IPpartition { my ( $array, $left, $right, $pivotIndex ) = @_; my $pivotValue = $array->[$pivotIndex]; #~ Move pivot to end #~ swap( $array->[$pivotIndex], $array->[$right] ); @{$array}[$pivotIndex, $right] = @{$array}[ $right, $pivotIndex]; my $storeIndex = $left; for my $i ( $left .. ( $right - 1 ) ) { # left = i < r +ight if ( $array->[$i] < $pivotValue ) { #~ swap( $array->[$i], $array->[$storeIndex] ); @{$array}[ $i, $storeIndex ] = @{$array}[$storeIndex , $i] +; $storeIndex = $storeIndex + 1; } } #~ Move pivot to its final place #~ swap( $array->[$storeIndex], $array->[$right] ); @{$array}[$storeIndex, $right] = @{$array}[$right, $storeIndex ]; return $storeIndex; } sub IPquicksortREF { my ($array, $left, $right) = ( @_, 0, 0 ); $right ||= $#$array; #~ If the list has 2 or more items if( $left < $right ){ #~ See "Choice of pivot" section below for possible choices #~ choose any $pivotIndex such that $left <= $pivotIndex <= $right my $pivotIndex = $left; #~ Get lists of bigger and smaller items and final position of pivot my $pivotNewIndex = IPpartition($array, $left, $right, $pivotI +ndex); #~ Recursively sort elements smaller than the pivot IPquicksortREF($array, $left, $pivotNewIndex - 1); #~ Recursively sort elements at least as big as the pivot IPquicksortREF($array, $pivotNewIndex + 1, $right ); } } sub p6quicksort { return @_ if @_ < 2; my( $pivot , @rest ) = @_; # Partition. my @before = grep { $_ < $pivot } @rest; my @after = grep { $_ >= $pivot } @rest; # Sort the partitions. return ( p6quicksort(@before), $pivot, p6quicksort(@after)); } sub DD { use Data::Dumper(); print STDERR Data::Dumper->new([@_])->Indent(0)->Dump, "\n"; } __END__ $VAR1 = [1,5,2,3,4]; $VAR1 = [1,2,3,4,5]; $VAR1 = [3,2,4,5,1]; $VAR1 = [1,2,3,4,5]; ################################# $VAR1 = [1,5,2,3,4]; $VAR1 = [1,2,3,4,5]; $VAR1 = [3,2,4,5,1]; $VAR1 = [1,2,3,4,5];

        Speedy Gonzales

      well, As I mentioned , something is broken.

Re: quicksort implementation
by flexvault (Parson) on Oct 05, 2011 at 14:54 UTC

    Did you try?

    perl -e 'my $ar = join( ",",sort(1,5,2,3,4) );print "[$ar];\n";'

    A lot less code and it's 100% perl!

    "Well done is better than well said." - Benjamin Franklin

      hello flexvault I was trying to implement this one as our perl destro doesnt have in build sort thanks
        What kind of Perl do you have?!

        What? So if you say perl -e 'print qq/$_\n/ for sort qw/c a d b n f/' what do you get?


        Dave

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://929763]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2014-09-02 01:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (18 votes), past polls