recursion with perl

Discussion in 'Perl' started by B McInnes, Nov 1, 2003.

  1. B McInnes

    B McInnes Guest

    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); }
    }
     
    B McInnes, Nov 1, 2003
    #1
    1. Advertising

  2. B McInnes

    Ugo Guest

    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
     
    Ugo, Nov 3, 2003
    #2
    1. Advertising

  3. B McInnes

    nikolay Guest

    ÷ ÐÉÓØÍÅ 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: -kpi.kiev.ua
    ICQ#: 136497739
     
    nikolay, Nov 3, 2003
    #3
  4. B McInnes

    Jim Gibson Guest

    In article <>, 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.
    >
    > 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.
     
    Jim Gibson, Nov 3, 2003
    #4
  5. B McInnes

    B McInnes Guest

    Jim Gibson <> wrote in message news:<031120031253405769%>...
    >
    > 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
     
    B McInnes, Nov 4, 2003
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dpackwood
    Replies:
    3
    Views:
    1,830
  2. Replies:
    16
    Views:
    194
    Ted Zlatanov
    Jun 5, 2006
  3. PerlFAQ Server

    FAQ 1.4 What are Perl 4, Perl 5, or Perl 6?

    PerlFAQ Server, Jan 23, 2011, in forum: Perl Misc
    Replies:
    0
    Views:
    313
    PerlFAQ Server
    Jan 23, 2011
  4. PerlFAQ Server
    Replies:
    0
    Views:
    708
    PerlFAQ Server
    Feb 3, 2011
  5. Replies:
    8
    Views:
    761
    John Reye
    Apr 26, 2012
Loading...

Share This Page