JetBrains Academy: Counting sort in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Counting sort in Java

Not only non-negative numbers:

Implement a method to sort a given array of ints using counting sort.

The method should process numbers from -10 to 20 inclusive.

Note: the method must change elements of the input array.

import java.util.*;

public class Main {

    public static void subZeroCountingSort(int[] numbers) {
        int[] borders = defineRange(numbers);
        int shift = Math.abs(borders[0]);
        int max = borders[1];

        int k = max + 1; // the length of the array containing counts
        int[] counts = new int[k + shift]; // it stores zeros with indexes from 0 to k-1 + shift

        /* in this loop we count distinct numbers in the input array */
        for (int number : numbers) {
            counts[number + shift]++;
        }

        int pos = 0; // a position in the numbers array

        /* in this loop we modify the input array to make it sorted */
        for (int num = 0; num < k + shift; num++) { // get the next element
            int count = counts[num]; // get the count of the element
            while (count > 0) {
                numbers[pos] = num - shift; // write it in the numbers array
                pos++;
                count--;
            }
        }

    }
    
    public static int[] defineRange(int[] numbers) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int number : numbers) {
            if (number > max) {
                max = number;
            }
            if (number < min) {
                min = number;
            }
        }

        return new int[] {min, max};
    }

    /* Do not change code below */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final String elements = scanner.nextLine();
        final int[] array = Arrays.stream(elements.split("\\s+"))
                                  .mapToInt(Integer::parseInt)
                                  .toArray();
        subZeroCountingSort(array);
        Arrays.stream(array).forEach(e -> System.out.print(e + " "));
    }
}

---

Sorting characters:

Write a program that sorts a given sequence of characters in the ascending order.

A sequence may include only the following characters: 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'.

It's recommended to use the counting sort algorithm. Other algorithms may get "Time limit exceeds" error.

Input data format: The first line contains the number of characters. The second one consists of characters.

Output data format: Output the characters in ascending order separated by space.

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.nextLine();
        int[] array = scanner.nextLine().chars().toArray();

        Arrays.stream(countingSort(array))
                .forEach(value -> System.out.print((char) value + " "));
        
    }
    
    public static int[] countingSort(int[] elements) {
        int maxValue = Integer.MIN_VALUE;

        for (int elem : elements) {
            if (elem > maxValue) {
                maxValue = elem;
            }
        }
        
        int k = maxValue + 1; // the length of the array containing counts
        int[] counts = new int[k]; // it stores zeros with indexes from 0 to k-1

        /* in this loop we count distinct elements in the input array */
        for (int elem : elements) {
            counts[elem]++;
        }

        int pos = 0; // a position in the elements array

        /* in this loop we modify the input array to make it sorted */
        for (int num = 0; num < k; num++) { // get the next element
            int count = counts[num]; // get the count of the element
            while (count > 0) {
                elements[pos] = num; // write it in the elements array
                pos++;
                count--;
            }
        }

        return elements;
    }
}

---