Class IntegerDBIDArrayQuickSort


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

    Two array iterators will be used to seek to the elements to compare, while the backing storage is a plain integer array.

    Reference:

    V. Yaroslavskiy
    Dual-Pivot Quicksort

    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.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static int compare​(IntegerDBIDVar i1, int p1, IntegerDBIDVar i2, int p2, java.util.Comparator<? super DBIDRef> comp)
      Compare two elements.
      private static void quickSort​(int[] data, int start, int end, java.util.Comparator<? super DBIDRef> comp, IntegerDBIDVar vl, IntegerDBIDVar vk, IntegerDBIDVar vr)
      Actual recursive sort function.
      static void sort​(int[] data, int start, int end, java.util.Comparator<? super DBIDRef> comp)
      Sort the array using the given comparator.
      static void sort​(int[] data, java.util.Comparator<? super DBIDRef> comp)
      Sort the full array using the given comparator.
      • 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 DBIDs.
        See Also:
        Constant Field Values
    • Constructor Detail

      • IntegerDBIDArrayQuickSort

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

      • sort

        public static void sort​(int[] data,
                                java.util.Comparator<? super DBIDRef> 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,
                                java.util.Comparator<? super DBIDRef> 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,
                                      java.util.Comparator<? super DBIDRef> comp,
                                      IntegerDBIDVar vl,
                                      IntegerDBIDVar vk,
                                      IntegerDBIDVar vr)
        Actual recursive sort function.
        Parameters:
        data - Data to sort
        start - First index
        end - Last index (inclusive!)
        comp - Comparator
        vl - First seeking iterator
        vk - Second seeking iterator
        vr - Third seeking iterator
      • compare

        private static int compare​(IntegerDBIDVar i1,
                                   int p1,
                                   IntegerDBIDVar i2,
                                   int p2,
                                   java.util.Comparator<? super DBIDRef> comp)
        Compare two elements.
        Parameters:
        i1 - First scratch variable
        p1 - Value for first
        i2 - Second scratch variable
        p2 - Value for second
        comp - Comparator
        Returns:
        Comparison result