javaalgorithmsortingdata-structurescounting-sort

Need help to understand an implementation of the Counting Sort sort algorithm


This code is about algorithms and datastructures. This code runs perfectly and i just have some questions on it because it seems like i don't understand two points. So my questions for that is:

  1. which informations are in the countingArray?
  2. how often is the while loop executed?

public class CountingSort {

    public static void main(String[] args) {
        int[] m1 = { 1, 17, 3, 1, 4, 9, 4, 4 };

        System.out.println("unsorted:");
        output(m1);
        int min1 = rangeMin(m1);
        int max1 = rangeMax(m1);

        countingSort(m1, min1, max1);
        System.out.println("sorted:");
        output(m1);

        int[] m2 = { -1, 13, 3, -1, -4, 9, -4, 4 };
        System.out.println("unsorted:");
        output(m2);
        int min2 = rangeMin(m2);
        int max2 = rangeMax(m2);

        countingSort(m2, min2, max2);
        System.out.println("sorted:");
        output(m2);
    }

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

    public static int rangeMin(int[] a) {
        int minimum = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < minimum)
                minimum = a[i];
        }
        return minimum;
    }

    public static int rangeMax(int[] array) {
        int maximum = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > maximum)
                maximum = array[i];
        }
        return maximum;
    }

    public static void countingSort(int[] array, int rangeMin, int rangeMax) {
        int[] countingArray = new int[rangeMax - rangeMin + 1];
        for (int i : array) {
            countingArray[i - rangeMin]++;
        }
        int c = 0;

        for (int i = rangeMin; i <= rangeMax; i++) {
            while (countingArray[i - rangeMin] > 0) {

                array[c] = i;
                c++;
                countingArray[i - rangeMin]--;
            }
        }
    }
}

Solution

  • CountingSort has O(n) time and space complexity. You iterate (i.e. use for loop) twice.

    public class CountingSort {
    
        public static void main(String... args) {
            proceed(1, 17, 3, 1, 4, 9, 4, 4);
            System.out.println("---");
            proceed(-1, 13, 3, -1, -4, 9, -4, 4);
        }
    
        public static void proceed(int... arr) {
            System.out.print("unsorted: ");
            print(arr);
    
            countingSort(arr);
    
            System.out.print("sorted:   ");
            print(arr);
        }
    
        public static void print(int... arr) {
            System.out.println(Arrays.stream(arr)
                                     .mapToObj(i -> String.format("%2d", i))
                                     .collect(Collectors.joining(",")));
        }
    
        public static void countingSort(int... arr) {
            int min = Arrays.stream(arr).min().orElse(0);
            int max = Arrays.stream(arr).max().orElse(0);
            // contains amount of number in the unsorted array
            // count[0] - amount of min numbers
            // count[count.length - 1] - amount of max numbers
            int[] count = new int[max - min + 1];
    
            for (int i : arr)
                count[i - min]++;
    
            // fill source array with amount of numbers
            for (int i = 0, j = 0; i < count.length; i++)
                for (int k = 0; k < count[i]; k++, j++)
                    arr[j] = min + i;
        }
    }