import-bot (20211) [Avatar] Offline
#1
[Originally posted by graham patterson]

Hi Andrew,

Well, I've worked my way right to the end of your truly superb book and gotten
every single code sample to work -- except one, so this is my last question on
this forum! Here goes: the original heap sort algorithm in chapter 17 works
fine, but I couldn't get the version using a recursive pushdown sub to work.
Here's what I have for the original:

#!/usr/bin/perl
use warnings;
use strict;

my @array = (7, 10, 5, 2, 6, 3, 1, 9, 4, smilie;
print "@array original
";
heap_sort(@array);
print "@array sorted
";

##### subs #####

sub heap_sort {
my $heap = @_;
unshift @$heap, scalar @_;
for (my $i = int($heap->[0] / 2); $i >= 1; $i--) {
pushdown($heap, $i);
}
for (my $i = $heap->[0]; $i >= 2; $i--) {
($heap->[1], $heap->[$i]) = ($heap->[$i], $heap->[1]);
# print "@array
"; # DEBUG
$heap->[0]--;
pushdown($heap, 1);
}
shift @$heap;
}

sub pushdown {
my ($heap, $i) = @_;
my $size = $heap->[0];
while ($i <= $size / 2) {
my $child = 2 * $i;
if ($child < $size and $heap->[$child] < $heap->[$child + 1]) {
$child++;
}
if ($heap->[$i] >= $heap->[$child]) { last; }
($heap->[$i], $heap->[$child]) = ($heap->[$child], $heap->[$i]);
$i = $child;
}
}

Now the above code works as advertised, giving output like this (with a print
statement added in the for loop as shown):

7 10 5 2 6 3 1 9 4 8 original
6 9 5 7 8 3 1 2 4 10
4 8 5 7 6 3 1 2 9 10
2 7 5 4 6 3 1 8 9 10
1 6 5 4 2 3 7 8 9 10
3 4 5 1 2 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 sorted

But when I try the same code using the recursive version of the pushdown sub
from the solutions to the exercises elsewhere on this site, instead of the
original, the sort doesn't work. Here's what I have for the recursive sub
version:

sub pushdown {
my $i = shift;
my $l = 2 * $i;
my $r = $l + 1;
my $largest = 0;
if ($l <= $_[0] and $_[$l] > $_[$i]) {
$largest = $l;
} else {
$largest = $i;
}
if ($r <= $_[0] and $_[$r] > $_[$largest]) {
$largest = $r;
}
if ($largest != $i) {
($_[$largest], $_[$i]) = ($_[$i], $_[$largest]);
unshift @_, $i;
&pushdown;
}
}

and here's the output (again with a print statement added):

7 10 5 2 6 3 1 9 4 8 original
8 10 5 2 6 3 1 9 4 7
4 10 5 2 6 3 1 9 8 7
9 10 5 2 6 3 1 4 8 7
1 10 5 2 6 3 9 4 8 7
3 10 5 2 6 1 9 4 8 7
6 10 5 2 3 1 9 4 8 7
2 10 5 6 3 1 9 4 8 7
5 10 2 6 3 1 9 4 8 7
10 5 2 6 3 1 9 4 8 7
10 5 2 6 3 1 9 4 8 7 sorted

So it looks like the code is not correctly identifying the largest element and
moving it to the end, then the next largest to end -1, etc. I've spent ages
trying to think my way through the problem, stepped through the code using the
debugger, etc, but finally I have to admit defeat. Do I need to modify the
program in some way, or have I just mistyped something somewhere?

Thanks as always for your help,
Graham
import-bot (20211) [Avatar] Offline
#2
Re: recursive pushdown sub in heap sort, ch17
[Originally posted by jandrew]

Graham,

The version of the recursive solution shown in the solution isn't
of the same structure as the the original --- it doesn't expect to
get the same arguments (it expects the index first and the array
passed in not as a reference ... it then modifies @_ to modify the
array). I am unsure how this version got in the solutions smilie

However, fixing this version to work with an array ref passed first
and then index is relatively simple: Add one line grabbing the $heap
to the top of the routine; change every occurence of $_[?] to use
$heap->[?] instead; drop the call unshifting @_ second from the bottom
and finally, recursively call: pushdown($heap, $largest). So it
becomes:

sub pushdown {
my $heap = shift;
my $i = shift;
my $l = 2 * $i;
my $r = $l + 1;
my $largest = 0;
if ($l <= $heap->[0] and $heap->[$l] > $heap->[$i]){
$largest = $l;
}else{
$largest = $i;
}
if ($r <= $heap->[0] and $heap->[$r] > $heap->[$largest]){
$largest = $r;
}
if ($largest != $i) {
($heap->[$largest],$heap->[$i]) = ($heap->[$i],$heap->[$largest]);
pushdown($heap,$largest);
}
}

I am glad you enjoyed the book inspite of its few warts. If we don't
see you here any longer, perhaps we'll see you over at perlmonks.org.
At any rate, have fun Perl'ing!

andrew

ps: a few titles I can recommend for further study:

Object Oriented Perl (Damian Conway)
Mastering Regular Expressions (Jeffrey Friedl)
Network Programming with Perl (Lincoln Stein)
import-bot (20211) [Avatar] Offline
#3
Re: recursive pushdown sub in heap sort, ch17
[Originally posted by graham patterson]

Thanks Andrew -- I made the changes as suggested to the recursive pushdown sub
and it works perfectly. It is a tribute to the quality of your book that, even
though it must be about 3 years old by now, every single sample of code can
still (with a bit of thought and some tweaking) be made to work!

Cheers, Graham