Class FunUtil.Quicksorter<T>

  • Enclosing class:
    FunUtil

    static class FunUtil.Quicksorter<T>
    extends java.lang.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?

    • Field Summary

      Fields 
      Modifier and Type Field Description
      int TOO_SMALL  
    • Constructor Summary

      Constructors 
      Constructor Description
      Quicksorter​(T[] vec, java.util.Comparator<T> comp)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void partialSort​(int limit)  
      void select​(int limit)
      puts the LIMIT biggest items at the head, not sorted
      void sort()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Quicksorter

        public Quicksorter​(T[] vec,
                           java.util.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)