Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > recursion with perl

Reply
Thread Tools

recursion with perl

 
 
B McInnes
Guest
Posts: n/a
 
      11-01-2003
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); }
}
 
Reply With Quote
 
 
 
 
Ugo
Guest
Posts: n/a
 
      11-03-2003
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
 
Reply With Quote
 
 
 
 
nikolay
Guest
Posts: n/a
 
      11-03-2003
В письме 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: http://www.velocityreviews.com/forums/(E-Mail Removed)-kpi.kiev.ua
ICQ#: 136497739

 
Reply With Quote
 
Jim Gibson
Guest
Posts: n/a
 
      11-03-2003
In article <(E-Mail Removed) >, B McInnes
<(E-Mail Removed)> 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.
 
Reply With Quote
 
B McInnes
Guest
Posts: n/a
 
      11-04-2003
Jim Gibson <(E-Mail Removed)> wrote in message news:<031120031253405769%(E-Mail Removed) >...
>
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
va_arg... recursion: changing arguments and the using recursion jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM
FAQ 2.17 What is perl.com? Perl Mongers? pm.org? perl.org? cpan.org? PerlFAQ Server Perl Misc 0 02-03-2011 11:00 AM
FAQ 1.4 What are Perl 4, Perl 5, or Perl 6? PerlFAQ Server Perl Misc 0 01-23-2011 05:00 AM
perldocs (etc) on recursion in Perl? Don't understand _WCPS_ example usenet@DavidFilmer.com Perl Misc 16 06-05-2006 06:05 PM
Perl Help - Windows Perl script accessing a Unix perl Script dpackwood Perl 3 09-30-2003 02:56 AM



Advertisments