Tie::Quicksort::Lazy - a lazy quicksort with tiearray interface
use Tie::Quicksort::Lazy TRIVIAL => 1023; tie my @producer, Tie::Quicksort::Lazy, @input; while (@producer){ my $first_remaining = shift @producer; ... }; use sort 'stable'; tie my @StableProducer, Tie::Quicksort::Lazy, \&comparator, @input; ...
A pure-perl lazy, stable, quicksort. The only defined way to access the resulting tied array is with shift.
shift
Sorting is deferred until an item is required.
Stability is maintained by choosing a pivot element randomly and treating equal elements differently in the before and after sections.
This module operates on a copy of the input array, which becomes the initial partition. As the partitions are divided, the old partitions are let go.
For a stable variant, tie to Tie::Quicksort::Lazy::Stable instead and use a stable perl sort for the trivial sort or set "TRIVIAL" to 1 on the use line.
when the first parameter is an unblessed coderef, that coderef will be used as the sort comparison function. The default is
sub { $_[0] cmp $_[1] }
Ergo, if you want to use this module to sort a list of coderefs, you will need to bless the first one.
A variable $trivial is defined which declares the size of a partition that we simply hand off to Perl's sort for sorting. by default, this is no longer used, but it is still available if you want it.
$trivial
this module was inspired by an employment interview question concerning the quicksort-like method of selecting the first k from n items ( see http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting )
Original version; created by h2xs 1.23 with options
-ACX -b 5.6.1 -n Tie::Quicksort::Lazy
revised to use perl arrays for partitioning operations instead of a confusing profusion of temporary index variables
revised internal data structure, no longer using perl's sort for anything by default, no longer scrambling input due to random pivot element selection.
Tie::Array::Sorted::Lazy is vaguely similar
David L. Nicol davidnico@cpan.org
Copyright (C) 2009 by the author
This library is free software; you may redistribute and/or modify it under the same terms as Perl.
To install Tie::Quicksort::Lazy, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Tie::Quicksort::Lazy
CPAN shell
perl -MCPAN -e shell install Tie::Quicksort::Lazy
For more information on module installation, please visit the detailed CPAN module installation guide.