Counting Sort

Counting sort is an out-of-place, non-comparison sorting algorithm that sorts a list with duplicate values efficiently. It is a helpful algorithm for sorting arrays of small, non-negative integers, where it analyzes elements’ frequency distribution and places them in their final sorted positions.

Explanation

1. Find the maximum value:

• Iterate through the input array data to find the largest element max.
  • This determines the range of values needed to be counted.

1. Create the count array:

• Initialize a new array count with a max + 1 size to hold each value’s frequency.
  • The size is max + 1 so that the max element is accounted for.
• Set all elements in count to 0 initially.

1. Count the occurrences:

• Loop through the data array again.
• For each element data[i], increment the corresponding count in the count array (count[data[i]]++).
  • This is to document the frequency distribution of elements in data.

1. Create the start array:

• Initialize a new array start of the same size as count.
• Set start[0] to 0.
• Based on the frequency distribution found in count, the starting indexes can be determined and stored in the start array (start[j] = start[j-1] + count[j-1] for j=1 to max).

1. Place elements in sorted order:

• Iterate through the data array again.
• For each element data[a]:
  • Retrieve its corresponding position to the temp variable from the start array (temp = start[data[a]]).
  • Place the element in the result array at that position (result[temp] = data[a]).
  • Increment the start value for the next element with the same value (start[data[a]]++).

1. Return the sorted array:

• The result array now contains the elements of the original data array in sorted order.
• Return the result array.

Implementation

The following example written in Java shows an implementation of counting sort:

import java.util.Random;
import java.util.Arrays;

public class CountingSorting {
    public static void main(String[] args) {
        Random rand = new Random();
        int[] arr1 = new int[10];
        for(int i =0; i < arr1.length; i++){
            arr1[i] = rand.nextInt(5);
        }
        System.out.println("Array Before Sort: " + Arrays.toString(arr1));
        System.out.println("Array After Sort: " + Arrays.toString(countingSort(arr1)));
    }
    public static int[] countingSort(int[] data){
        int[] count,start,result;
        result = new int[data.length];
        //Step #1
        int max = Integer.MIN_VALUE;
        for(int item:data)
        {
            max = Math.max(max,item);
        }
        //Step #2
        count = new int[max+1];
        //Step #3
        for(int i = 0; i < data.length; i++){
            count[data[i]]++;
        }
        //Step #4
        start = new int[max+1];
        start[0]= 0;
        for(int j =1; j < start.length; j++){
            start[j] = start[j-1] + count[j-1];
        }
        //Step #5
        for(int a = 0; a < result.length;a++){
            int temp = start[data[a]];
            result[temp] = data[a];
            start[data[a]]++;
        }
        //Step #6
        return result;
    }

}

The output for the above code is:

Array Before Sort: [3, 2, 1, 4, 2, 4, 2, 1, 4, 2]
Array After Sort:  [1, 1, 2, 2, 2, 2, 3, 4, 4, 4]

Time Complexity

• The first and third loops run in O(k) time, where k is max.
• The second and last loops run in O(n) time.
• Therefore, the total running time is O(n+k).
• If k = O(n), then the total time is O(n).