How Counting Kind Work in Java? Instance Tutorial

How Counting Kind Algorithms Work?

Because the identify suggests Counting Kind algorithm kinds an array of integer by counting how variety of instances a singular factor seem within the array. It woks finest when your array accommodates small optimistic integers, also referred to as keys on this case.   

Since sorting algorithms are finest understood by seeing sorting in motion,  here’s a YouTube tutorial which explains how Counting Kind works with instance, you’ll be able to watch this video a few instances to grasp how Counting Kind kinds components as its not a straightforward one which you’ll be able to grasp in only one minute, chances are you’ll be nevertheless it took me a few instances to essentially get this into my head.

You may watch this YouTube tutorial proper right here, its from CS Dojo or you’ll be able to watch it on CS Dojo channel on YouTube, one in every of my favourite channels. 

Java Program to Implement Counting Kind Algorithm

Right here is an instance of doing counting type in Java. 

import java.util.Arrays;

/**
 * Java Program to type an array of integers with Counting Kind algorithm.
 * Counting Kind is a linear time sorting algorithm, which reap the benefits of
 * favorable situation to type an inventory of integers in O(n) time.
 *
 * @creator WINDOWS 8
 */
public class CountingSort {

    public static void major(String args[]) {

        // sorting integer array utilizing Counting Kind
        int[] random = {4, 8, 3, 2, 9, 3, 11};
        System.out.println("Unsorted random integer array : "
                               + Arrays.toString(random));

        countingsort(random, 11);
        System.out.println("Sorted integer array : "
                             + Arrays.toString(random));

        // yet another instance
        int[] massive = {332, 44, 32, 99, 11, 119, 434, 33};
        System.out.println("Unsorted array of integers : " 
                             + Arrays.toString(massive));

        countingsort(massive, 434);
        System.out.println("Sorted integer array : "
                             + Arrays.toString(massive));
    }

    /*
     * Types integer array utilizing Counting Kind Algorithm
     * time complexity : Greatest Case O(n+ok); Common Case O(n+ok); 
     * Worst Case O(n+ok),
     * the place n is the scale of the enter array and ok means the
     * values vary from 0 to ok.
     */
    public static void countingsort(int[] enter, int ok) {
        // create buckets
        int counter[] = new int[k + 1];

        // fill buckets
        for (int i : enter) {
            counter[i]++;
        }

        // type array
        int ndx = 0;
        for (int i = 0; i < counter.size; i++) {
            whereas (0 < counter[i]) {
                enter[ndx++] = i;
                counter[i]--;
            }
        }
    }
}

Output :
Unsorted random integer array : [4, 8, 3, 2, 9, 3, 11]
Sorted integer array : [2, 3, 3, 4, 8, 9, 11]
Unsorted array of integers : [332, 44, 32, 99, 11, 119, 434, 33]
Sorted integer array : [11, 32, 33, 44, 99, 119, 332, 434]

That is all about the right way to implement counting type in Java. It is one of many O(n) sorting algorithms also referred to as linear time sorting algorithm and fall into class of non-comparison sorting algorithm. This implies you type numbers with out evaluating them.