Package elki.utilities.datastructures.arrays

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