Name: Hrafnkell Freyr Hlodversson
Email: [EMAIL PROTECTED]
Preferred user-ID: HRAFNKELL
Description:
A module that implements a sorting algorithm I saw in an old paper by
István Beck and Stein Krogdahl called "Select And Insert Sort". This
module was originally done to try out the Inline module by Brian Ingerson,
but is now fairly usable - if not only as a working demonstration of
the virtues of Inline::C.
The algorithim is a combination of Straight Insertion Sort and Selection
Sort. While Insertion Sort and Selection Sort both are of complexity
O(n**2), Select and Insert Sort should be of complexitiy O(n**1.5).
Module name: Algorithm::SISort
Description: Implementation of Select And Insert sorting algorithm in C
DSLI: Rdcr
... and here is the POD, scissored from the module:
=head1 NAME
Algorithm::SISort - Implementation of Select And Insert sorting algorithm
in C
=head1 SYNOPSIS
use Algorithm::SISort qw(Sort Sort_inplace);
@sorted_list = Sort {$_[0] <=> $_[1]} @unsorted_list;
# ... or ...
Sort_inplace {$_[0] <=> $_[1]} @unsorted_list;
=head1 DESCRIPTION
This module implements a sorting algorithm I saw in BIT 28 (1988) by
István Beck and Stein Krogdahl. This implmentation is mainly intended to
try out the Inline module by Brian Ingerson. The algorithim is a
combination of I<Straight Insertion Sort> and I<Selection Sort>. While
I<Insertion Sort> and I<Selection Sort> both are of complexity O(n**2),
I<Select and Insert Sort> should have complexitiy O(n**1.5).
This module defines the functions C<Sort> and C<Sort_inplace>, which have
signatures similar to the internal C<sort> function. The difference is
that a codref defining a comparison is always required and that the two
values to compare are always passed in C<@_> and not as C<$a> and C<$b>.
(Although I might change that later.)
C<Sort> returns a sorted copy if the array, but C<Sort_inplace> sorts the
array in place (as the name suggests) and returns the number of
comparisons done. (Note that the sorting is always done in place, C<Sort>
just copies the array before calling the internal sort routine.)
=head1 SEE ALSO
L<Inline>, L<Inline::C>, and I<A Select And Insert Sorting Algorithm> by
István Beck and Stein Krogdahl in I<BIT 28 (1988), 726-735>.
=head1 AUTHOR
Hrafnkell F. Hlodversson, [EMAIL PROTECTED]
=head1 COPYRIGHT
Copyright 2001, Hrafnkell F Hlodversson
All Rights Reserved. This module is free software. It may
be used, redistributed and/or modified under the terms of
the Perl Artistic License.
See http://www.perl.com/perl/misc/Artistic.html
=cut
--
With kind regads
Keli H F Hlodversson
I used to think that anything was possible if I'd just tried hard
enough... That's how I got my first restraining order.
-- Sturla Tabta
