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