469,568 Members | 1,483 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,568 developers. It's quick & easy.

recursion with perl

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); }
}
Jul 19 '05 #1
4 5759
Ugo
On Sat, 01 Nov 2003 15:03:02 +0000, B McInnes wrote:
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__

--
Ugo
Jul 19 '05 #2
В письме 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.

--
With best wishes Nikolay
mail: ni*****@asu.ntu-kpi.kiev.ua
ICQ#: 136497739

Jul 19 '05 #3
In article <75**************************@posting.google.com >, B McInnes
<bt*******@yahoo.com> wrote:
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.
Jul 19 '05 #4
Jim Gibson <jg*****@mail.arc.nasa.gov> wrote in message news:<031120031253405769%jg*****@mail.arc.nasa.gov >...

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
Jul 19 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Peri | last post: by
1 post views Thread by Tim Mohler | last post: by
12 posts views Thread by da Vinci | last post: by
43 posts views Thread by Lorenzo Villari | last post: by
75 posts views Thread by Sathyaish | last post: by
13 posts views Thread by Mumia W. | last post: by
20 posts views Thread by athar.mirchi | last post: by
1 post views Thread by sharathdotbv | last post: by
35 posts views Thread by Muzammil | last post: by
reply views Thread by suresh191 | last post: by
4 posts views Thread by guiromero | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.