Class IntegerArrayQuickSort


  • @Reference(authors="V. Yaroslavskiy",
               title="Dual-Pivot Quicksort",
               booktitle="",
               url="http://iaroslavski.narod.ru/quicksort/",
               bibkey="web/Yaroslavskiy09")
    public class IntegerArrayQuickSort
    extends java.lang.Object
    Class to sort an int array, using a modified quicksort.

    Reference:

    The implementation is closely based on:

    Vladimir Yaroslavskiy
    Dual-Pivot Quicksort

    and differs mostly in that we sort different kinds of arrays, and allow the use of comparators - useful in particular when the array references external objects.

    Since:
    0.5.5
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int INSERTION_THRESHOLD
      Threshold for using insertion sort.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private IntegerArrayQuickSort()
      Private constructor.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static void insertionSort​(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
      Insertion sort, for short arrays.
      private static void quickSort​(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
      Actual recursive sort function.
      static void sort​(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
      Sort the array using the given comparator.
      static void sort​(int[] data, it.unimi.dsi.fastutil.ints.IntComparator comp)
      Sort the full array using the given comparator.
      private static void sort5​(int[] data, int m1, int m2, int m3, int m4, int m5, it.unimi.dsi.fastutil.ints.IntComparator comp)
      An explicit sort, for the five pivot candidates.
      • Methods inherited from class java.lang.Object

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

      • INSERTION_THRESHOLD

        private static final int INSERTION_THRESHOLD
        Threshold for using insertion sort. Value taken from Javas QuickSort, assuming that it will be similar for our data sets.
        See Also:
        Constant Field Values
    • Constructor Detail

      • IntegerArrayQuickSort

        private IntegerArrayQuickSort()
        Private constructor. Static methods only.
    • Method Detail

      • sort

        public static void sort​(int[] data,
                                it.unimi.dsi.fastutil.ints.IntComparator comp)
        Sort the full array using the given comparator.
        Parameters:
        data - Data to sort
        comp - Comparator
      • sort

        public static void sort​(int[] data,
                                int start,
                                int end,
                                it.unimi.dsi.fastutil.ints.IntComparator comp)
        Sort the array using the given comparator.
        Parameters:
        data - Data to sort
        start - First index
        end - Last index (exclusive)
        comp - Comparator
      • quickSort

        private static void quickSort​(int[] data,
                                      int start,
                                      int end,
                                      it.unimi.dsi.fastutil.ints.IntComparator comp)
        Actual recursive sort function.
        Parameters:
        data - Data to sort
        start - First index
        end - Last index (exclusive!)
        comp - Comparator
      • insertionSort

        private static void insertionSort​(int[] data,
                                          int start,
                                          int end,
                                          it.unimi.dsi.fastutil.ints.IntComparator comp)
        Insertion sort, for short arrays.
        Parameters:
        data - Data to sort
        start - First index
        end - Last index (exclusive!)
        comp - Comparator
      • sort5

        private static void sort5​(int[] data,
                                  int m1,
                                  int m2,
                                  int m3,
                                  int m4,
                                  int m5,
                                  it.unimi.dsi.fastutil.ints.IntComparator comp)
        An explicit sort, for the five pivot candidates.

        Note that this must only be used with m1 < m2 < m3 < m4 < m5.

        Parameters:
        data - Data
        m1 - Pivot candidate position
        m2 - Pivot candidate position
        m3 - Pivot candidate position
        m4 - Pivot candidate position
        m5 - Pivot candidate position
        comp - Comparator