Counting sort

Sort the array by counting the frequencies of each element.

Example:

Input:  arr[]={3, 2, 4, 4, 3, 1, 2, 6, 5, 5, 4, 3 }
Output: arr[]={1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6}

Approach

Java

import java.util.Arrays;
import java.util.HashMap;

public class CountingSort {
    public static void main(String[] args) {
        int arr[] = { 3, 2, 4, 4, 3, 1, 2, 6, 5, 5, 4, 3 };
        int N = arr.length;
        countingSort(arr, N);
        System.out.println(Arrays.toString(arr));
    }

    private static void countingSort(int[] arr, int N) {
        int MAXN = 0;

        // find the maximum element
        // in the array
        for (int i = 0; i < N; i++)
            MAXN = Math.max(MAXN, arr[i]);

        // freq count map
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();

        // count the frequency of each
        // element
        for (int i = 0; i < N; i++)
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);

        int index = 0;

        // sort the array on the basis
        // of the counts
        for (int i = 0; i <= MAXN; i++) {
            while (freq.containsKey(freq.get(i)) && freq.get(i) > 0) {
                arr[index++] = i;
                freq.put(i, freq.get(i) - 1);
            }
        }

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to sort the array
//using counting sort
void counting_sort(int arr[],int N)
{
    int MAXN=0;

    //find the maximum element
    //in the array
    for(int i=0;i<N;i++)
       MAXN=max(MAXN,arr[i]);

    //make the array of size maximum element +1
    int freq[MAXN+1];
    for(int i=0;i<=MAXN;i++)
      freq[i]=0;

    //count the frequency of each
    //element
    for(int i=0;i<N;i++)
      freq[arr[i]]++;
    int index=0;

    //sort the array on the basis
    //of the counts
    for(int i=0;i<=MAXN;i++)
      {

          while(freq[i]>0)
            {
                arr[index++]=i;
                freq[i]--;
            }
      }
    
}
int main()
{
    int arr[]={3,2,4,4,3,1,2,6,5,5,4,3};
    int N=sizeof(arr)/sizeof(arr[0]);
    counting_sort(arr,N);
    for(int i=0;i<N;i++)
       cout<<arr[i]<<" ";
    return 0;
}