Counting Sort in Java

Yasin Cakal

Counting sort is an efficient algorithm for sorting a collection of objects according to their frequencies. It is a non-comparative sorting algorithm that uses a counting array to sort the elements. Counting sort is particularly useful when the elements of the collection are known to be in a certain range. This means that the number of distinct elements in the collection is known and is relatively small. Counting sort is often used in situations where the range of values is small and the collection is large.

Counting sort works by counting the number of times each element occurs in the collection and then using this information to place the elements in their correct positions in the sorted collection. The algorithm is simple and efficient, taking linear time (O(n)) to run. Counting sort can also be used to determine the frequencies of elements in the collection.

How Counting Sort Works

Counting sort works by counting the number of times each element appears in the collection and then using this information to place the element in its correct position in the sorted collection. The algorithm works by creating an array of integers, where each index in the array corresponds to an element in the collection. The algorithm then counts the number of times each element appears in the collection and stores this information in the corresponding index in the array.

After the count array is created, the algorithm then iterates through the collection and places each element in its correct position in the sorted collection. The algorithm works by finding the count of the element in the count array and then placing the element in its correct position in the sorted array.

Time Complexity

Counting sort is an efficient sorting algorithm, taking linear time (O(n)) to run, where n is the size of the collection. The algorithm is simple and efficient, taking linear time (O(n)) to run.

The time complexity for access, search, insertion and deletion are all O(n) for Counting sort. This is because access, search, insertion and deletion all require a single iteration through the collection.

Space Complexity

The space complexity of Counting sort is O(n+k), where n is the size of the collection and k is the range of values in the collection. This is because Counting sort requires additional space in the form of a count array. The count array needs to be at least as large as the range of values in the collection.

Java Code Example

The following Java code example demonstrates how Counting sort works. The code creates an array of random integers and then sorts them using Counting sort.

public static void main(String[] args) {

    // create an array of random integers 
    int[] array = new int[10];
    for (int i = 0; i < 10; i++) {
        array[i] = (int) (Math.random() * 10 + 1);
    }

    // print the array 
    System.out.println("Unsorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

    // sort the array 
    countingSort(array, 10);

    // print the sorted array 
    System.out.println("Sorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

}

public static void countingSort(int[] array, int range) {

    // create a count array to store the count of each element 
    int[] count = new int[range];

    // store the count of each element 
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // modify the count array such that each element at each index 
    // stores the sum of previous counts 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // create the output array 
    int[] output = new int[array.length];

    // store the element from the input array as per 
    // the count array and place it in output array 
    for (int i = array.length - 1; i >= 0; i--) {
        output[count[array[i] - 1] - 1] = array[i];
        count[array[i] - 1]--;
    }

    // copy the sorted elements into original array 
    System.arraycopy(output, 0, array, 0, array.length);

}

Conclusion

In conclusion, Counting sort is an efficient algorithm for sorting a collection of objects according to their frequencies. It is a non-comparative sorting algorithm that uses a counting array to sort the elements. Counting sort is particularly useful when the elements of the collection are known to be in a certain range. The algorithm is simple and efficient, taking linear time (O(n)) to run. The time complexity for access, search, insertion and deletion are all O(n) for Counting sort. The space complexity of Counting sort is O(n+k), where n is the size of the collection and k is the range of values in the collection.

Exercises

Write a Java program to create an array of random integers and then sort them using Counting sort.

public static void main(String[] args) {

    // create an array of random integers 
    int[] array = new int[10];
    for (int i = 0; i < 10; i++) {
        array[i] = (int) (Math.random() * 10 + 1);
    }

    // sort the array 
    countingSort(array, 10);

    // print the sorted array 
    System.out.println("Sorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

}

public static void countingSort(int[] array, int range) {

    // create a count array to store the count of each element 
    int[] count = new int[range];

    // store the count of each element 
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // modify the count array such that each element at each index 
    // stores the sum of previous counts 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // create the output array 
    int[] output = new int[array.length];

    // store the element from the input array as per 
    // the count array and place it in output array 
    for (int i = array.length - 1; i >= 0; i--) {
        output[count[array[i] - 1] - 1] = array[i];
        count[array[i] - 1]--;
    }

    // copy the sorted elements into original array 
    System.arraycopy(output, 0, array, 0, array.length);

}

Write a Java program to create an array of integers and then sort them using Counting sort.

public static void main(String[] args) {

    // create an array of integers 
    int[] array = {6, 4, 3, 2, 5, 1};

    // print the array 
    System.out.println("Unsorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

    // sort the array 
    countingSort(array, 6);

    // print the sorted array 
    System.out.println("Sorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

}

public static void countingSort(int[] array, int range) {

    // create a count array to store the count of each element 
    int[] count = new int[range];

    // store the count of each element 
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // modify the count array such that each element at each index 
    // stores the sum of previous counts 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // create the output array 
    int[] output = new int[array.length];

    // store the element from the input array as per 
    // the count array and place it in output array 
    for (int i = array.length - 1; i >= 0; i--) {
        output[count[array[i] - 1] - 1] = array[i];
        count[array[i] - 1]--;
    }

    // copy the sorted elements into original array 
    System.arraycopy(output, 0, array, 0, array.length);

}

Write a Java program to find the frequency of each element in an array and then sort them using Counting sort.

public static void main(String[] args) {

    // create an array of integers 
    int[] array = {6, 4, 3, 2, 5, 1};

    // print the array 
    System.out.println("Unsorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

    // find the frequency of each element 
    int[] count = new int[6];
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // print the frequency of each element 
    System.out.println("Frequency of each element: ");
    for (int i = 0; i < count.length; i++) {
        System.out.println("Element " + (i + 1) + " appears " + count[i] + " times.");
    }

    // sort the array 
    countingSort(array, 6);

    // print the sorted array 
    System.out.println("Sorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

}

public static void countingSort(int[] array, int range) {

    // create a count array to store the count of each element 
    int[] count = new int[range];

    // store the count of each element 
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // modify the count array such that each element at each index 
    // stores the sum of previous counts 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // create the output array 
    int[] output = new int[array.length];

    // store the element from the input array as per 
    // the count array and place it in output array 
    for (int i = array.length - 1; i >= 0; i--) {
        output[count[array[i] - 1] - 1] = array[i];
        count[array[i] - 1]--;
    }

    // copy the sorted elements into original array 
    System.arraycopy(output, 0, array, 0, array.length);

}

Write a Java program to create an array of integers and then find the minimum and maximum elements in the array using Counting sort.

public static void main(String[] args) {

    // create an array of integers 
    int[] array = {6, 4, 3, 2, 5, 1};

    // print the array 
    System.out.println("Unsorted array: ");
    for (int num : array) {
        System.out.print(num + " ");
    }
    System.out.println();

    // sort the array 
    countingSort(array, 6);

    // find the minimum and maximum elements in the array 
    int min = array[0];
    int max = array[array.length - 1];

    // print the minimum and maximum elements 
    System.out.println("Minimum element: " + min);
    System.out.println("Maximum element: " + max);

}

public static void countingSort(int[] array, int range) {

    // create a count array to store the count of each element 
    int[] count = new int[range];

    // store the count of each element 
    for (int i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }

    // modify the count array such that each element at each index 
    // stores the sum of previous counts 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // create the output array 
    int[] output = new int[array.length];

    // store the element from the input array as per 
    // the count array and place it in output array 
    for (int i = array.length - 1; i >= 0; i--) {
        output[count[array[i] - 1] - 1] = array[i];
        count[array[i] - 1]--;
    }

    // copy the sorted elements into original array 
    System.arraycopy(output, 0, array, 0, array.length);

}

Data Structures and Algorithms with Java

Participants 681