Untitled

**Counting Sort** is a non-comparison-based sorting algorithm that sorts integers (or objects that can be mapped to integers) by counting the occurrences of each value in the input and using this count to place elements in the correct sorted position. 

Unlike comparison-based sorting algorithms like QuickSort or MergeSort, Counting Sort achieves a time complexity of \( O(n + k) \), where \( n \) is the number of elements in the input array and \( k \) is the range of input values.

---

### **How Counting Sort Works**

#### **1. Assumptions**
- The input consists of integers within a known range \([0, k]\), where \( k \) is the maximum value in the array.
- It is most effective when \( k \) is not significantly larger than \( n \).

#### **2. Steps**
1. **Counting Frequencies**:
   - Create a frequency array (`count[]`) of size \( k+1 \).
   - Populate `count[i]` with the number of occurrences of \( i \) in the input array.

2. **Cumulative Counts**:
   - Compute the cumulative frequency to determine the position of each element in the sorted array.

3. **Build the Sorted Array**:
   - Iterate through the input array in reverse order (to ensure stability).
   - Place each element in its correct position in the output array using the cumulative counts, and decrement the corresponding count.

---

### **Algorithm in Detail**
Given an input array \( \text{arr}[] \) of size \( n \):

1. **Step 1: Find the Range**:
   - Determine the maximum value \( k \) in the input array.

2. **Step 2: Initialize the Count Array**:
   - Create a `count[]` array of size \( k+1 \) and initialize it to zero.

3. **Step 3: Populate the Count Array**:
   - For each element \( x \) in \( \text{arr}[] \), increment `count[x]`.

4. **Step 4: Compute Cumulative Counts**:
   - Transform `count[]` into a cumulative frequency array:
     \[
     \text{count}[i] = \text{count}[i] + \text{count}[i-1]
     \]

5. **Step 5: Sort the Array**:
   - Traverse the input array in reverse order to maintain stability.
   - Place each element \( x \) at the position `count[x]-1` in the output array and decrement `count[x]`.

6. **Step 6: Copy Back**:
   - Copy the sorted output array back to the original input array if needed.

---

### **Java Implementation**
```java
public class CountingSort {
    public static void countingSort(int[] arr) {
        int n = arr.length;

        // Step 1: Find the maximum value
        int max = 0;
        for (int num : arr) {
            max = Math.max(max, num);
        }

        // Step 2: Create and populate the count array
        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }

        // Step 3: Compute cumulative counts
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // Step 4: Build the output array
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // Step 5: Copy back to original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);

        // Print the sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
```

---

### **Example Walkthrough**
#### Input: \( \text{arr}[] = [4, 2, 2, 8, 3, 3, 1] \)

1. **Count Frequencies**:
   - \( \text{count}[] = [0, 1, 2, 2, 1, 0, 0, 0, 1] \)

2. **Cumulative Counts**:
   - \( \text{count}[] = [0, 1, 3, 5, 6, 6, 6, 6, 7] \)

3. **Sort the Array**:
   - Traverse \( \text{arr}[] \) backward and build the sorted array:
     - \( \text{output}[] = [1, 2, 2, 3, 3, 4, 8] \)

4. **Copy Back**:
   - Final \( \text{arr}[] = [1, 2, 2, 3, 3, 4, 8] \).

---

### **Key Properties**
1. **Time Complexity**:
   - \( O(n + k) \), where \( n \) is the input size, and \( k \) is the range of values.

2. **Space Complexity**:
   - \( O(n + k) \), due to the count array and the output array.

3. **Stability**:
   - Counting Sort is stable if elements are placed into the output array in reverse order.

4. **Not Comparison-Based**:
   - Sorting is done via counting and indexing, not comparisons.

---

### **Limitations**
1. **Limited to Integer Values**:
   - Works best for integers or discrete values that can be mapped to integers.
   
2. **Range Dependency**:
   - If \( k \) (the range) is significantly larger than \( n \), Counting Sort becomes inefficient in terms of space and time.

3. **Not In-Place**:
   - Requires additional space for the count and output arrays.

---

### **When to Use Counting Sort**
- Use Counting Sort when:
  - The range of input values (\( k \)) is small compared to the number of elements (\( n \)).
  - Stability is required (e.g., sorting by one key while maintaining the order of another key).

Examples include sorting grades, event counts, or low-range discrete datasets efficiently.