Class Sorter

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected Sorter()
      Sole constructor, used for inheritance.
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void binarySort​(int from, int to)
      A binary sort implementation.
      (package private) void binarySort​(int from, int to, int i)  
      (package private) void checkRange​(int from, int to)  
      protected abstract int compare​(int i, int j)
      Compare entries found in slots i and j.
      protected int comparePivot​(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).
      (package private) void doRotate​(int lo, int mid, int hi)  
      (package private) static int heapChild​(int from, int i)  
      (package private) void heapify​(int from, int to)  
      (package private) static int heapParent​(int from, int i)  
      (package private) void heapSort​(int from, int to)
      Use heap sort to sort items between from inclusive and to exclusive.
      (package private) int lower​(int from, int to, int val)  
      (package private) int lower2​(int from, int to, int val)  
      (package private) void mergeInPlace​(int from, int mid, int to)  
      (package private) void reverse​(int from, int to)  
      (package private) void rotate​(int lo, int mid, int hi)  
      protected void setPivot​(int i)
      Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
      (package private) void siftDown​(int i, int from, int to)  
      abstract void sort​(int from, int to)
      Sort the slice which starts at from (inclusive) and ends at to (exclusive).
      protected abstract void swap​(int i, int j)
      Swap values at slots i and j.
      (package private) int upper​(int from, int to, int val)  
      (package private) int upper2​(int from, int to, int val)  
      • Methods inherited from class java.lang.Object

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

      • pivotIndex

        private int pivotIndex
    • Constructor Detail

      • Sorter

        protected Sorter()
        Sole constructor, used for inheritance.
    • Method Detail

      • compare

        protected abstract int compare​(int i,
                                       int j)
        Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).
      • swap

        protected abstract void swap​(int i,
                                     int j)
        Swap values at slots i and j.
      • setPivot

        protected void setPivot​(int i)
        Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
      • comparePivot

        protected int comparePivot​(int j)
        Compare the pivot with the slot at j, similarly to compare(i, j).
      • sort

        public abstract void sort​(int from,
                                  int to)
        Sort the slice which starts at from (inclusive) and ends at to (exclusive).
      • checkRange

        void checkRange​(int from,
                        int to)
      • mergeInPlace

        void mergeInPlace​(int from,
                          int mid,
                          int to)
      • lower

        int lower​(int from,
                  int to,
                  int val)
      • upper

        int upper​(int from,
                  int to,
                  int val)
      • lower2

        int lower2​(int from,
                   int to,
                   int val)
      • upper2

        int upper2​(int from,
                   int to,
                   int val)
      • reverse

        final void reverse​(int from,
                           int to)
      • rotate

        final void rotate​(int lo,
                          int mid,
                          int hi)
      • doRotate

        void doRotate​(int lo,
                      int mid,
                      int hi)
      • binarySort

        void binarySort​(int from,
                        int to)
        A binary sort implementation. This performs O(n*log(n)) comparisons and O(n^2) swaps. It is typically used by more sophisticated implementations as a fall-back when the numbers of items to sort has become less than 20.
      • binarySort

        void binarySort​(int from,
                        int to,
                        int i)
      • heapSort

        void heapSort​(int from,
                      int to)
        Use heap sort to sort items between from inclusive and to exclusive. This runs in O(n*log(n)) and is used as a fall-back by IntroSorter.
      • heapify

        void heapify​(int from,
                     int to)
      • siftDown

        void siftDown​(int i,
                      int from,
                      int to)
      • heapParent

        static int heapParent​(int from,
                              int i)
      • heapChild

        static int heapChild​(int from,
                             int i)