Implementation of Counting sort in Java.

In this Java tutorial, we will learn about counting sort. And, we will also learn the implementation of counting sort in java.

We have several algorithms that can sort n numbers in O(n log(n) ) time. Merge sort and heap sort algorithms achieve this complexity in the worst case. Quicksort sorts n number numbers in n*logn time in the average case. All these algorithms are comparison based sorting algorithms. Any comparison sort must make n*logn comparisons in the worst case to sort n elements.

Counting Sort

It is not a comparison sort. It uses the actual values of elements as an index and is based on the count of their occurrences. The assumption of counting sort is that each input element is in the range 0 to k. When k= O(n), the sort runs in linear time as asymptotically tight bound. It is a very efficient sorting algorithm when the range of values in the array is small. There are mainly three steps in this algorithm:

  1. We determine the count of each element in the array and store it in count array C[0… k].
  2. Then, we modify array C to now store the number of elements less than or equal to x, for each element x.
  3. We use the above array to place element x directly into its position in the output array.

 Variables needed in the Implementation

  • The size of input array n.
  • Input array A[0.. n]
  • A temporary array C[0…k] where k is the maximum range of the input elements.
  • An output array B[0.. n] which stores the output sorted array.

 

Implementation of Counting sort in Java

import java.util.Scanner;

public class CountingSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the size of the array n: ");
        int n = sc.nextInt();

        int[] A = new int[n];
        int[] C = new int[n + 1];

        System.out.println("Enter the elements of the array in the range 0 to n: ");
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
            C[A[i]] = C[A[i]] + 1;
        }
        // C[i] contains the number of elements equal to i
        System.out.print("Array C:  ");
        printArray(C);
        int[] B = new int[n];

        for (int i = 1; i <= n; i++) {
            C[i] += C[i - 1];
        }
        System.out.print("Array C:  ");
        printArray(C);
        // C[i] contains the number of elements less than or equal to i

        for (int i = A.length - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]] = C[A[i]] - 1;

            System.out.print("Array B:  " );
            printArray(B);

            System.out.print("Array C:  ");
            printArray(C);
        }

    }

    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Input

Enter the size of the array n: 
6
Enter the elements of the array in the range 0 to n: 
1 5 2 3 5 2

Output

Array C: 0 1 2 1 0 2 0 
Array C: 0 1 3 4 4 6 6 
Array B: 0 0 2 0 0 0 
Array C: 0 1 2 4 4 6 6 
Array B: 0 0 2 0 0 5 
Array C: 0 1 2 4 4 5 6 
Array B: 0 0 2 3 0 5 
Array C: 0 1 2 3 4 5 6 
Array B: 0 2 2 3 0 5 
Array C: 0 1 1 3 4 5 6 
Array B: 0 2 2 3 5 5 
Array C: 0 1 1 3 4 4 6 
Array B: 1 2 2 3 5 5 
Array C: 0 0 1 3 4 4 6

 

The last for loop places each element A[i] into its correct position in array B. The counting sort runs in a linear time when the elements have a low range of values. An important property of this algorithm is that it is stable. It means that numbers with the same value appear in the output array in the same order as in input array.

You can also read:

 



Leave a Reply

Your email address will not be published. Required fields are marked *