Re: Sorting Arrays Without using SORT function

[Fletch]

in reply to Sorting Arrays Without using SORT function

Sure, but runtime depends on your luck.

#!/usr/bin/env perl
use strict;
use warnings;
use List::Util qw( shuffle reduce );

my @list = qw( f a d e z x c b );

sub in_order {
  my $state = 1;
  our( $a, $b );
  my $ordered = reduce { if( $state and $b lt $a ) { $state = undef; }
+ $b } @_;
  return $state;
}

my $shuffles = 0;
my @ordered = @list;
my %memory;
until ( in_order( @ordered ) ) {
  $memory{ join("\0",@ordered) } = 1;
  while( 1 ) {
    @ordered = shuffle( @list );
    $shuffles++;
    last unless $memory{ join("\0",@ordered) };
  }
}

print "took $shuffles shuffles to get\n\t", join( "\n\t", @ordered ), 
+"\n";

exit 0;

__END__

[SuicideJunkie]

If PC isn't allowed to use the sort function, then List::Util is probably even more forbidden.

use strict;
use warnings;

my @array = qw(h o m e w o r k);
while (not isSorted(@array))
{
  print +(join ", ", @array) . "\r";
  my ($x, $y) = (rand(scalar @array), rand(scalar @array));
  ($array[$x], $array[$y]) = ($array[$y], $array[$x]);
}
print "\nSort complete!\n";
print join ", ", @array;

sub isSorted
{
  my $x = shift;
  while (my $y = shift)
  {
    return 0 unless ($x cmp $y) < 1;
    $x = $y;
  }
  return 1;
}