NAME
Tie::Quicksort::Lazy - a lazy quicksort with tiearray interface
SYNOPSIS
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::Stable, \&comparator, @input;
...DESCRIPTION
A pure-perl lazy quicksort. The only defined way to access the resulting tied array is with shift.
Sorting is deferred until an item is required.
memory use
This module operates on a copy of the input array.
Internal copies are made during the partitioning process to greatly improve readability, instead of doing in-place swaps and tracking a lot of array indices. Future releases of this module, if any, may do it differently.
So initially the Tie::Quicksort::Lazy object will include an array the size of the input array, and the first partitioning will use a temporary array that size too. Later partitions will be smaller. Since the first partitioning is deferred until the first shift operation, if we have enough memory to build the object, and then forget about the input, we will have enough memory to partition it.
tie my @LazySorted, Tie::Quicksort::Lazy get_unsorted_data();
while (@LazySorted) {
my $first = shift @LazySorted;
...
};stability
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.
BYO (Bring Your Own) comparator
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.
trivial partition
A constant trivial is defined which declares the size of a partition that we simply hand off to Perl's sort for sorting. This defaults to 127.
INSPIRATION
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 )
HISTORY
- 0.01
-
Original version; created by h2xs 1.23 with options
-ACX -b 5.6.1 -n Tie::Quicksort::Lazy - 0.02
-
revised to use perl arrays for partitioning operations instead of a confusing profusion of temporary index variables
SEE ALSO
Tie::Array::Sorted::Lazy is vaguely similar
AUTHOR
David L. Nicol davidnico@cpan.org
COPYRIGHT AND LICENSE
Copyright (C) 2009 by the author
This library is free software; you may redistribute and/or modify it under the same terms as Perl.