#!/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];
