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, \&comparator,  @input;
  ...

DESCRIPTION

A pure-perl lazy, stable, quicksort. The only defined way to access the resulting tied array is with 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.

memory use

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.

trivial partitions

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 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.

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

0.04

revised internal data structure, no longer using perl's sort for anything by default, no longer scrambling input due to random pivot element selection.

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.