Package org.ddogleg.sorting

Class CountingSort

java.lang.Object
org.ddogleg.sorting.CountingSort
public class CountingSort extends Object
A O(N) sorting routine for integer valued elements with a known upper and lower bound. This performance can be obtained since it does not compare elements and instead create a histogram.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CountingSort()
     
    CountingSort(int minValue, int maxValue)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    setRange(int minValue, int maxValue)
    Specify the data range
    void
    sort(int[] data, int begin, int end)
    Sorts the data in the array.
    void
    sort(int[] input, int startIndex, int[] output, int startOutput, int length)
    Sort routine which does not modify the input array.
    void
    sortIndex(int[] input, int start, int length, int[] indexes)
    Sort routine which does not modify the input array and instead maintains a list of indexes.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CountingSort

      public CountingSort()

    • CountingSort

      public CountingSort(int minValue, int maxValue)

  • Method Details

    • setRange

      public void setRange(int minValue, int maxValue)
      Specify the data range
      Parameters:
      minValue - Minimum allowed value. (inclusive)
      maxValue - Maximum allowed value. (inclusive)

    • sort

      public void sort(int[] data, int begin, int end)
      Sorts the data in the array.
      Parameters:
      data - Data which is to be sorted. Sorted data is written back into this same array
      begin - First element to be sorted (inclusive)
      end - Last element to be sorted (exclusive)

    • sort

      public void sort(int[] input, int startIndex, int[] output, int startOutput, int length)
      Sort routine which does not modify the input array. Input and output arrays can be the same instance.
      Parameters:
      input - (Input) Data which is to be sorted. Not modified.
      startIndex - First element in input list
      output - (Output) Sorted data. Modified.
      length - Number of elements

    • sortIndex

      public void sortIndex(int[] input, int start, int length, int[] indexes)
      Sort routine which does not modify the input array and instead maintains a list of indexes.
      Parameters:
      input - (Input) Data which is to be sorted. Not modified.
      start - First element in input list
      length - Length of the input list
      indexes - Number of elements