Class Sorting

java.lang.Object
org.apache.commons.numbers.arrays.Sorting

final class Sorting extends Object
Support class for sorting arrays.

Optimal sorting networks are used for small fixed size array sorting.

Note: Requires that the floating-point data contains no NaN values; sorting does not respect the order of signed zeros imposed by Double.compare(double, double).

Since:
1.2
See Also:
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    No instances.
  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) static int
    insertionSortIndices(int[] x, int n)
    Sort the unique indices in-place to the start of the array.
    (package private) static void
    lowerMedian4(double[] x, int a, int b, int c, int d)
    Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
    (package private) static void
    lowerMedian4(int[] x, int a, int b, int c, int d)
    Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
    (package private) static void
    sort(double[] x, int left, int right)
    Sorts an array using an insertion sort.
    (package private) static void
    sort(int[] x, int left, int right)
    Sorts an array using an insertion sort.
    (package private) static void
    sort3(double[] x, int a, int b, int c)
    Sorts the elements at the given distinct indices in an array.
    (package private) static void
    sort3(int[] x, int a, int b, int c)
    Sorts the elements at the given distinct indices in an array.
    (package private) static void
    sort5(double[] x, int a, int b, int c, int d, int e)
    Sorts the elements at the given distinct indices in an array.
    (package private) static void
    sort5(int[] x, int a, int b, int c, int d, int e)
    Sorts the elements at the given distinct indices in an array.
    (package private) static int
    sortIndices(int[] x, int n)
    Sort the unique indices in-place to the start of the array.
    (package private) static void
    upperMedian4(double[] x, int a, int b, int c, int d)
    Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
    (package private) static void
    upperMedian4(int[] x, int a, int b, int c, int d)
    Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • Sorting

      private Sorting()
      No instances.
  • Method Details

    • sort

      static void sort(double[] x, int left, int right)
      Sorts an array using an insertion sort.
      Parameters:
      x - Data array.
      left - Lower bound (inclusive).
      right - Upper bound (inclusive).
    • sort3

      static void sort3(double[] x, int a, int b, int c)
      Sorts the elements at the given distinct indices in an array.
      Parameters:
      x - Data array.
      a - Index.
      b - Index.
      c - Index.
    • sort5

      static void sort5(double[] x, int a, int b, int c, int d, int e)
      Sorts the elements at the given distinct indices in an array.
      Parameters:
      x - Data array.
      a - Index.
      b - Index.
      c - Index.
      d - Index.
      e - Index.
    • lowerMedian4

      static void lowerMedian4(double[] x, int a, int b, int c, int d)
      Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
      Parameters:
      x - Values
      a - Index.
      b - Index.
      c - Index.
      d - Index.
    • upperMedian4

      static void upperMedian4(double[] x, int a, int b, int c, int d)
      Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
      Parameters:
      x - Values
      a - Index.
      b - Index.
      c - Index.
      d - Index.
    • sort

      static void sort(int[] x, int left, int right)
      Sorts an array using an insertion sort.
      Parameters:
      x - Data array.
      left - Lower bound (inclusive).
      right - Upper bound (inclusive).
    • sort3

      static void sort3(int[] x, int a, int b, int c)
      Sorts the elements at the given distinct indices in an array.
      Parameters:
      x - Data array.
      a - Index.
      b - Index.
      c - Index.
    • sort5

      static void sort5(int[] x, int a, int b, int c, int d, int e)
      Sorts the elements at the given distinct indices in an array.
      Parameters:
      x - Data array.
      a - Index.
      b - Index.
      c - Index.
      d - Index.
      e - Index.
    • lowerMedian4

      static void lowerMedian4(int[] x, int a, int b, int c, int d)
      Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
      Parameters:
      x - Values
      a - Index.
      b - Index.
      c - Index.
      d - Index.
    • upperMedian4

      static void upperMedian4(int[] x, int a, int b, int c, int d)
      Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
      Parameters:
      x - Values
      a - Index.
      b - Index.
      c - Index.
      d - Index.
    • insertionSortIndices

      static int insertionSortIndices(int[] x, int n)
      Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

      Uses an insertion sort modified to ignore duplicates. Use on small n.

      Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

      Parameters:
      x - Indices.
      n - Number of indices.
      Returns:
      the number of unique indices
    • sortIndices

      static int sortIndices(int[] x, int n)
      Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

      Uses an Order(1) data structure to ignore duplicates.

      Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

      Parameters:
      x - Indices.
      n - Number of indices.
      Returns:
      the number of unique indices