Package elki.database.ids.integer

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