Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
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 taking refuge in the Monastery: (11)
As of 2014-09-23 23:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (241 votes), past polls