recursion with perl

[B McInnes]

Hello, I am working on creating a perl implementatin of quick sort, I
know that there is a perl sort function but I am doing this so that I
can later sort a vec based on the information in another vec.

I have tried my program with: perl v5.8.0 for sun4-solaris and perl
v5.6.1 for MSWin32-x86-multithread.

I wrote an implementation of quicksort in C++ and it works. I then
wrote it in Perl and it doesn't work. I can not see what is wrong with
it. It does not seem to sort the entire list unless the list is
completely backwards (ie 9876...). Maybe I have been at if for to
long. Any help would be greatly appreciated. I pasted my perl code
below.

Thanks!
B

CODE:
#!/usr/local/bin/perl

#@stack = (); was using to see what was comming into q_sort

$N = 99;

for $i(0..$N-1) { $numbers[$i] = int(rand(9)); }

print "@numbers\n\n";

quickSort();

print "@numbers\n\n";
#print "@stack\n";


sub quickSort { &q_sort(0, $N); }

sub q_sort
{
$left = shift;
$right = shift;

#push @stack, $left;
#push @stack, $right;

$l = $left; $r = $right;
$pivot = $numbers[$left];

while ($left < $right)
{
while (($numbers[$right] >= $pivot) && ($left <
$right)) {
$right--;
}
if ($left != $right) {
$numbers[$left] = $numbers[$right]; $left++;
}
while (($numbers[$left] <= $pivot) && ($left <
$right)) {
$left++;
}
if ($left != $right) {
$numbers[$right] = $numbers[$left]; $right--;
}
}
$numbers[$left] = $pivot;
$pivot = $left;
$left = $l; $right = $r;

if ($left < $pivot) { &q_sort($left, $pivot-1); }
if ($right > $pivot) { &q_sort($pivot+1, $right); }
}

 

[Ugo]

Hello, I am working on creating a perl implementatin of quick sort, I know
that there is a perl sort function but I am doing this so that I can later
sort a vec based on the information in another vec.

You can use sort even with other rules for the comparison,
in such a way:
sort { # block of code examining the special variables $a and $b
# and returning -1, 0 or 1 with some rule of comparison
....
} # No punctation between the block and the list
@list_to_be_sorted ;

Example:
#!/usr/bin/perl
%age = ( Anne => 34,
Marco => 23,
Tamara => 31,
Susan => 26,
Alessandra => 16,
);
@name = keys %age;
@name = sort { $age{$a} <=> $age{$b} } @name;
print "People ordered by age:\n";
print "$_ is $age{$_} years old.\n" for @name;
__END__

 

[nikolay]

÷ ÐÉÓØÍÅ Sat, 01 Nov 2003 15:03:02 -0800, B McInnes ÎÁÐÉÓÁÌ:

Hello, I am working on creating a perl implementatin of quick sort, I

....
Thats good idea about removing stack, but next lines:

$left = shift;
$right = shift;

are also modification
....

$l = $left; $r = $right;
$pivot = $numbers[$left];
....
$numbers[$left] = $pivot;
$pivot = $left;
$left = $l; $right = $r;

if ($left < $pivot) { &q_sort($left, $pivot-1); }

now $right can be something other

if ($right > $pivot) { &q_sort($pivot+1, $right); }

....
I don't readed this example, so this is only first view tips.
I didn't wrote any recursion without stack of states, excep for
task where it isn't need. I think you can use $_[0] & $_[1] as $left &
$right.

 

[Jim Gibson]

Hello, I am working on creating a perl implementatin of quick sort, I
know that there is a perl sort function but I am doing this so that I
can later sort a vec based on the information in another vec.

I have tried my program with: perl v5.8.0 for sun4-solaris and perl
v5.6.1 for MSWin32-x86-multithread.

I wrote an implementation of quicksort in C++ and it works. I then
wrote it in Perl and it doesn't work. I can not see what is wrong with
it. It does not seem to sort the entire list unless the list is
completely backwards (ie 9876...). Maybe I have been at if for to
long. Any help would be greatly appreciated. I pasted my perl code
below.

Thanks!
B

By not declaring $left, $right, and $pivot as lexically local to the
q_sort subroutine with the "my" qualifier, they are global to your
program. Therefore, when they are modified by the first call to q_sort,
the values of $right and $pivot passed to q_sort in the second call are
not what they should be.

You should put "use strict;" at the beginning of your program to
prevent uninteded use of global variables. Then declare variables with
'our', 'local', or 'my' as appropriate or use package names

CODE:
#!/usr/local/bin/perl

#@stack = (); was using to see what was comming into q_sort

$N = 99;

for $i(0..$N-1) { $numbers[$i] = int(rand(9)); }

print "@numbers\n\n";

quickSort();

print "@numbers\n\n";
#print "@stack\n";


sub quickSort { &q_sort(0, $N); }

sub q_sort
{
$left = shift;

my $left = shift;

$right = shift;

my $right = shift;

#push @stack, $left;
#push @stack, $right;

$l = $left; $r = $right;
$pivot = $numbers[$left];

my $pivot = $numbers[$left];

while ($left < $right)
{
while (($numbers[$right] >= $pivot) && ($left <
$right)) {
$right--;
}
if ($left != $right) {
$numbers[$left] = $numbers[$right]; $left++;
}
while (($numbers[$left] <= $pivot) && ($left <
$right)) {
$left++;
}
if ($left != $right) {
$numbers[$right] = $numbers[$left]; $right--;
}
}
$numbers[$left] = $pivot;
$pivot = $left;
$left = $l; $right = $r;

if ($left < $pivot) { &q_sort($left, $pivot-1); }
if ($right > $pivot) { &q_sort($pivot+1, $right); }
}

FYI: this newsgroup is defunct. Use comp.lang.perl.misc in the future.

HTH.

 

[B McInnes]

By not declaring $left, $right, and $pivot as lexically local to the
q_sort subroutine with the "my" qualifier, they are global to your
program. Therefore, when they are modified by the first call to q_sort,
the values of $right and $pivot passed to q_sort in the second call are
not what they should be.

You should put "use strict;" at the beginning of your program to
prevent uninteded use of global variables. Then declare variables with
'our', 'local', or 'my' as appropriate or use package names

Thank you! I am not feeling very bright right now. I really appreciate
your help!!

FYI: this newsgroup is defunct. Use comp.lang.perl.misc in the future.

Thanks for letting me know. I will post on the above one for now on.
Hopefully, I will have a more intelligent question when the time comes


B