view release on metacpan or  search on metacpan

lib/Algorithm/Networksort.pm  view on Meta::CPAN

			for (my $i=$lo + $r; $i + $r < $lo + $n; $i += $m)
			{
				$add_elem->($i, $i + $r);
			}
		}
		else
		{
			$add_elem->($lo, $lo + $r);
		}
	};

	$sort->(0, 1 << $t);

	return @network;
}

#
# $array_ref = $nw->sort(\@array);
#
# Use the network of comparators to sort the elements in the
# array.  Returns the reference to the array, which is sorted
# in-place.
#
# This function is for testing and statistical purposes only, as
# interpreting sorting pairs ad hoc in an interpreted language is
# going to be very slow.
#
=head3 sort()

Sort an array using the network. This is meant for testing purposes
only - looping around an array of comparators in order to sort an
array in an interpreted language is not the most efficient mechanism
for using a sorting network.

This function uses the C<< <=> >> operator for comparisons.

    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my $nw = Algorithm::Networksort->new(
                        inputs => (scalar @digits),
                        algorithm => 'hibbard');
    $nw->sort(\@digits);
    print join(", ", @digits);

=cut

sub sort
{
	my $self = shift;
	my $array  = $_[0];

	my $network = $self->network();

	#
	### sort():
	##### $network
	##### $array
	#

	#
	# Variable $swaps is a global variable that reports back the
	# number of exchanges.
	#
	$swaps = 0;
	for my $comparator (@$network)
	{
		my($left, $right) = @$comparator;

		if (($$array[$left] <=> $$array[$right]) == 1)
		{
			@$array[$left, $right] = @$array[$right, $left];
			$swaps++;
		}

		#
		###### @$array
		#
	}

	return $array;
}

=head3 statistics()

Return statistics on the last sort() call. Currently only "swaps",
a count of the number of exchanges, is returned.

    my(@d, %nw_stats);
    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my $inputs = scalar @digits;
    my $nw_batcher = Algorithm::Networksort->new(inputs => $inputs, algorithm => 'batcher');
    my $nw_bn = Algorithm::Networksort->new(inputs => $inputs, algorithm => 'bosenelson');

    #
    # List will wind up sorted, so copy it for our first test run.
    #
    @d = @digits;
    $nw_batcher->sort(\@d);
    %nw_stats = $nw_batcher->statistics();
    print "The Batcher Merge-Exchange network took ",
        $nw_stats{swaps}, " exchanges to sort the array."

    @d = @digits;
    $nw_bn->sort(\@d);
    %nw_stats = $nw_bn->statistics();
    print "The Bose-Nelson network took ",
        $nw_stats{swaps}, " exchanges to sort the array."

=cut

sub statistics
{
	return (swaps => $swaps,
		);
}

=head2 Methods For Printing

The network object by default prints itself in a grouped format; that is

    my $nw = nwsrt(inputs => 8, algorithm => 'bosenelson');