Class FunUtil.Quicksorter<T>

  • Enclosing class:
    FunUtil

    static class FunUtil.Quicksorter<T>
    extends Object
    A functional for FunUtil.partialSort(T[], java.util.Comparator<T>, int). Sorts or partially sorts an array in ascending order, using a Comparator.

    Algorithm: quicksort, or partial quicksort (alias "quickselect"), Hoare/Singleton. Partial quicksort is quicksort that recurs only on one side, which is thus tail-recursion. Picks pivot as median of three; falls back on insertion sort for small "subfiles". Partial quicksort is O(n + m log m), instead of O(n log n), where n is the input size, and m is the desired output size.

    See D Knuth, Art of Computer Programming, 5.2.2 (Algorithm Q); R. Sedgewick, Algorithms in C, ch 5. Good summary in http://en.wikipedia.org/wiki/Selection_algorithm

    TODO: What is the time-cost of this functor and of the nested Comparators?

    • Constructor Detail

      • Quicksorter

        public Quicksorter​(T[] vec,
                           Comparator<T> comp)
    • Method Detail

      • sort

        public void sort()
      • select

        public void select​(int limit)
        puts the LIMIT biggest items at the head, not sorted
      • partialSort

        public void partialSort​(int limit)