view release on metacpan or  search on metacpan

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

algorithm creates very efficient networks in both comparators and stages.

=item 'bubble'

Use a naive bubble-sort/insertion-sort algorithm. Since this algorithm
produces more comparison pairs than the other algorithms, it is only
useful for illustrative purposes.

=item 'oddeventrans'

Use a naive odd-even transposition sort. This is a primitive sort closely
related to bubble sort except that it is more parallel. Because other
algorithms are more efficient, this sort is included for illustrative
purposes.

=item 'balanced'

This network is described in the 1983 paper "The Balanced Sorting Network"
by M. Dowd, Y. Perl, M Saks, and L. Rudolph. It is not a particularly
efficient sort but it has some interesting properties due to the fact
that it is constructed as a series of successive identical sub-blocks,
somewhat like with 'oddeventrans'.

=item 'none'

Do not generate a set of comparators. Instead, take the set from an
outside source, using the C<comparators> option.

    #
    # Test our own 5-input network.
    #
    @cmptr = ([1,2], [0,2], [0,1], [3,4], [0,3], [1,4], [2,4], [1,3], [2,3]);

    $nw = Algorithm::Networksort->new(inputs => 5,
                algorithm => 'none',
                comparators => [@cmptr]);

Internally, this is what L<nwsrt_best()|Algorithm::Networksort::Best/nwsrt_best()>
of L<Algorithm::Networksort::Best> uses.

=back

=item 'comparators'

The list of comparators provided by the user instead of by an algorithm.

=back

=cut

sub BUILD
{
	my $self = shift;
	my $alg = $self->algorithm();
	my $inputs = $self->inputs();

	my @network;
	my @grouped;

	#
	# Catch errors
	#
	croak "Input size must be 2 or greater" if ($inputs < 2);

	#
	# Providing our own-grown network?
	#
	if ($alg eq 'none')
	{
		croak "No comparators provided" unless ($self->has_comparators);
		$self->length(scalar @{ $self->comparators });

		#
		# Algorithm::Networksort::Best will set these, so
		# only go through with this if this is a user-provided
		# sequence of comparators.
		#
		unless ($self->has_network and $self->depth > 0)
		{
			@grouped = $self->group();
			$self->network($self->comparators);
			$self->depth(scalar @grouped);
			$self->network([map { @$_ } @grouped]);
			$self->title("Unknown $inputs-Inputs Comparator Set") unless ($self->has_title());
		}

		$self->nwid("nonalgorithmic-" . sprintf("%02d", $inputs)) unless ($self->has_nwid());

		return $self;
	}

	croak "Unknown algorithm '$alg'" unless (exists $algname{$alg});
	$self->nwid($alg . sprintf("%02d", $inputs));

	@network = bosenelson($inputs) if ($alg eq 'bosenelson');
	@network = hibbard($inputs) if ($alg eq 'hibbard');
	@network = batcher($inputs) if ($alg eq 'batcher');
	@network = bitonic($inputs) if ($alg eq 'bitonic');
	@network = bubble($inputs) if ($alg eq 'bubble');
	@network = oddeventransposition($inputs) if ($alg eq 'oddeventrans');
	@network = balanced($inputs) if ($alg eq 'balanced');
	@network = oddevenmerge($inputs) if ($alg eq 'oddevenmerge');

	$self->title($algname{$alg}  . " for N = " . $inputs) unless ($self->has_title);
	$self->length(scalar @network);
	$self->comparators(\@network);	# The 'raw' list of comparators.

	#
	# Re-order the comparator list using the parallel grouping for
	# the graphs. The resulting parallelism means less stalling
	# when used in a pipeline.
	#
	@grouped = $self->group();

	#
	###### @grouped
	#
	$self->depth(scalar @grouped);
	$self->network([map { @$_ } @grouped]);

	return $self;

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

		{
			$old_settings{$k} = $textset{$k};
			$textset{$k} = $settings{$k};
		}
		else
		{
			carp "textsettings(): Unknown key '$k'";
		}
	}

	return %old_settings;
}

#
# @newlist = semijoin($expr, $itemcount, @list);
#
# $expr      - A string to be used in a join() call.
# $itemcount - The number of items in a list to be joined.
#              It may be negative.
# @list      - The list
#
# Create a new list by performing a join on I<$itemcount> elements at a
# time on the original list. Any leftover elements from the end of the
# list become the last item of the new list, unless I<$itemcount> is
# negative, in which case the first item of the new list is made from the
# leftover elements from the front of the list.
#
sub semijoin
{
	my($jstr, $itemcount, @oldlist) = @_;
	my(@newlist);

	return @oldlist if ($itemcount <= 1 and $itemcount >= -1);

	if ($itemcount > 0)
	{
		push @newlist, join $jstr, splice(@oldlist, 0, $itemcount)
			while @oldlist;
	}
	else
	{
		$itemcount = -$itemcount;
		unshift @newlist, join $jstr, splice(@oldlist, -$itemcount, $itemcount)
		    while $itemcount <= @oldlist;
		unshift @newlist, join $jstr, splice( @oldlist, 0, $itemcount)
		    if @oldlist;
	}

	return @newlist;
}

1;
__END__

=head1 ACKNOWLEDGMENTS

L<Doug Hoyte|https://github.com/hoytech> provided the code for the bitonic,
odd-even merge, odd-even transposition, balanced, and bubble sort algorithms,
and the idea for what became the L<statistics()> method.

L<Morwenn|https://github.com/Morwenn> found documentation errors and networks
that went into L<Algorithm::Networksort::Best>.

=head1 SEE ALSO

=head2 Bose and Nelson's algorithm.

=over 3

=item

Bose and Nelson, "A Sorting Problem", Journal of the ACM, Vol. 9, 1962, pp. 282-296.

=item

Joseph Celko, "Bose-Nelson Sort", Doctor Dobb's Journal, September 1985.

=item

Frederick Hegeman, "Sorting Networks", The C/C++ User's Journal, February 1993.

=item

Joe Celko, I<Joe Celko's SQL For Smarties> (third edition). Implementing
Bose-Nelson sorting network in SQL.

This material isn't in either the second or fourth edition of the book.

=item

Joe Celko, I<Joe Celko's Thinking in Sets: Auxiliary, Temporal, and Virtual Tables in SQL>.

The sorting network material removed from the third edition of
I<SQL For Smarties> seems to have been moved to this book.

=back

=head2 Hibbard's algorithm.

=over 3

=item

T. N. Hibbard, "A Simple Sorting Algorithm", Journal of the ACM Vol. 10, 1963, pp. 142-50.

=back

=head2 Batcher's Merge Exchange algorithm.

=over 3

=item

Code for Kenneth Batcher's Merge Exchange algorithm was derived from Knuth's
The Art of Computer Programming, Vol. 3, section 5.2.2.

=back

=head2 Batcher's Bitonic algorithm

=over 3