Counting Sort Algorithm in Java

Today, we are going to show the implementation of the Counting sort algorithm, which is the forth one from our series of tutorials on sorting algorithms. If you haven’t read the first three tutorials on BubbleSortInsertionSort and SelectionSort, I strongly recommend that you read them, because we will reuse code that was explained there.

The application is really simple, it will just get an instance of a Sortable algorithm, which in this case will be a CountingSort object and pass some Integer and String arrays to it, but unlike the other three algorithms that are able to sort any object that implements Comparable, this algorithm only works with Integers (positive and negative values), the arrays of String will be ignored. The last part of the code is to print the sorted arrays.

public class SorterApp {
  public static void main(String[] args) {
    SorterApp app = new SorterApp();
    app.run();
  }

  private void run() {
    sort(new Integer[] { 2, 42, -3, 2, 4 });
    sort(new Integer[] { 1, 2, 3, 4, 5 });
    sort(new Integer[] { 3, 1, 5, 4, 2 });
    sort(new Integer[] { 5, 4, 3, 2, 1 });

    System.out.println();

    sort(new String[] { "a", "b", "c", "d", "e" });
    sort(new String[] { "c", "a", "e", "d", "b" });
    sort(new String[] { "e", "d", "c", "b", "a" });
  }

  private <T extends Comparable<T>> void sort(T[] values) {
    Sortable sorter = newSortable(4);
    sorter.sortAscending(values);
    // sorter.sortDescending(values);
    Utils.printArray(values);
  }

  private Sortable newSortable(int sortableAlgorithm) {
    switch (sortableAlgorithm) {
      case 1:
        return new BubbleSort();
      case 2:
        return new InsertionSort();
      case 3:
        return new SelectionSort();
      case 4:
        return new CountingSort();
      default:
        return new BubbleSort();
    }
  }
}


You can see on the code below that the sortAscending and sortDescending invoke the same private method sort with the difference of 1 parameter. This is done because the code to sort in ascending or descending order is pretty much the same; the difference is just one small detail.

The Sorter Abstract class and the Sortable Interface were explained on the first tutorial of our series.

public class SelectionSort extends Sorter implements Sortable {
  @Override
  public <T extends Comparable<T>> void sortAscending(T[] values) {
    sort(values, 0);
  }

  @Override
  public <T extends Comparable<T>> void sortDescending(T[] values) {
    sort(values, 1);
  }

Because counting sort uses key values as indexes into an array, it is not a comparison sort algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

  private <T extends Comparable<T>> void sort(T[] values, int orderType) {
    if (!(values instanceof Integer[])) {
      System.out.println("Only Integer arrays can be sorted by the Counting Sort algorithm.");
    } else {
      // If the array is null or has the size of 1, it means it is already sorted.
      if ((null == values) || (values.length < 2)) {
        return;
      }

      Integer[] temp = (Integer[]) values;
      int count = 0;
      int indexToInsertElement = 0;

      RangeElements rangeElements = Utils.getLowestAndHighestElement(temp);
      // The above method will iterate over all the elements in the array.
      count += temp.length;

      int lowestElement = rangeElements.getLowestElement();
      int highestElement = rangeElements.getHighestElement();
      // (highestElement - lowestElement) + 1 => It will be the possible range of the elements.
      int[] occurrences = new int[(highestElement - lowestElement) + 1];

      // Iterate through the array and count how many times each value has appeared and increment by
      // 1 every time.
      for (int i = 0; i < values.length; i++) {
        occurrences[temp[i] - lowestElement] += 1;
        count++;
      }

      // This peace of code is necessary just because we only want to create one method that will
      // sort ascending and descending, otherwise this code could be deleted.
      int currentIndex = 0;
      int finishIndex = 0;
      int increment = 0;
      if (0 == orderType) {
        // Ascending.
        currentIndex = 0;
        finishIndex = occurrences.length;
        increment = 1;
      } else if (1 == orderType) {
        // Descending.
        currentIndex = occurrences.length - 1;
        finishIndex = -1;
        increment = -1;
      }

      while (currentIndex != finishIndex) {
        int nrOccurrences = occurrences[currentIndex];
        count++;

        for (int j = 0; j < nrOccurrences; j++) {
          // It is necessary to "+ lowestElement" to compensate when it was subtracted.
          temp[indexToInsertElement++] = currentIndex + lowestElement;
          count++;
        }

        currentIndex += increment;
      }

      System.out.printf("%2s: ", count);
    }
  }
}

Results:

Counting Sort Results

You can download all the files here: CountingSort.

Thank you for your time and feel free to leave any comments or questions.

References:
http://en.wikipedia.org/wiki/Counting_sort
http://www.youtube.com/watch?v=_q0OOXo4l7E

Tweet about this on TwitterShare on StumbleUponShare on Google+Share on LinkedInShare on Facebook

3 Responses to “Counting Sort Algorithm in Java”

  1. Merge Sort Algorithm using Generics in Java - The Code Master Says:

    […] Counting Sort Algorithm in Java […]

  2. Vankudoth Ramesh Says:

    sir, I want to count “How many times the sorting technique goes and counts the number till the sorting is done “. I just want to know and advice me best site where I can find solution to my problem. I want to learn from the site.
    Because we were thought nothing our college life.

  3. Luciano Sampaio Says:

    Hi Vankudoth Ramesh,

    My algorithm already counts that for you but if you want to learn more about “Counting Sort”, check: https://en.wikipedia.org/wiki/Counting_sort

    Best regards,
    Luciano Sampaio

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.