counting Sort

XXX. Counting Sort

Sorting

Hash Map

Problem Statement:

Implement the counting sort algorithm to sort an array of integers. Counting sort uses a hash map to count the occurrences of each value, then reconstructs the sorted array by iterating through the keys in sorted order.

Algorithm:

1. Initialize a hash map to count occurrences of each integer in the array.
2. Find the minimum and maximum values in the array.
3. Iterate through the hash map in order of the keys (from minimum to maximum) to reconstruct the sorted array.

Complexity:

Time Complexity: O(n + k), where n is the number of elements in the array and k is the range of input values.
Space Complexity: O(k) for the hash map.

Java Implementation:

class Solution {
    private void countingSort(int[] arr) {
        // Create the counting hash map.
        HashMap counts = new HashMap<>();
        int minVal = arr[0], maxVal = arr[0];

        // Find the minimum and maximum values in the array, and update counts.
        for (int num : arr) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int index = 0;
        // Place each element in its correct position in the array.
        for (int val = minVal; val <= maxVal; val++)
            while (counts.getOrDefault(val, 0) > 0) {
                arr[index++] = val;
                counts.put(val, counts.get(val) - 1);
            }
    }

    public int[] sortArray(int[] nums) {
        countingSort(nums);
        return nums;
    }
}
                

Python Implementation:

def counting_sort(arr):
    counts = {}
    min_val, max_val = arr[0], arr[0]

    # Count occurrences and track min and max values
    for num in arr:
        min_val = min(min_val, num)
        max_val = max(max_val, num)
        counts[num] = counts.get(num, 0) + 1

    index = 0
    # Reconstruct the sorted array
    for val in range(min_val, max_val + 1):
        while counts.get(val, 0) > 0:
            arr[index] = val
            index += 1
            counts[val] -= 1

def sort_array(nums):
    counting_sort(nums)
    return nums
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

void countingSort(vector& arr) {
    unordered_map counts;
    int minVal = arr[0], maxVal = arr[0];

    // Count occurrences and track min and max values
    for (int num : arr) {
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
        counts[num]++;
    }

    int index = 0;
    // Reconstruct the sorted array
    for (int val = minVal; val <= maxVal; val++)
        while (counts[val] > 0) {
            arr[index++] = val;
            counts[val]--;
        }
}

vector sortArray(vector& nums) {
    countingSort(nums);
    return nums;
}