YouTipPython Counting Sort
## Python Counting Sort
Counting Sort is a non-comparison-based sorting algorithm. Its core mechanism relies on mapping the values of the input data to keys in an auxiliary array (often called the count array) to track occurrences.
As a linear-time complexity sorting algorithm, Counting Sort requires the input data to consist of integers (or elements that can be mapped to integers, such as characters) within a specific, well-defined range.
---
## How Counting Sort Works
Unlike comparison-based sorting algorithms (such as Quick Sort or Merge Sort) which compare elements against each other, Counting Sort works by counting the number of objects having distinct key values.
The general process is as follows:
1. **Find the Range:** Identify the maximum and minimum values in the input array to determine the size of the auxiliary `count` array.
2. **Count Occurrences:** Iterate through the input array and record the frequency of each value in the `count` array.
3. **Accumulate Sums:** Modify the `count` array by adding the previous counts. This transforms the array so that each index stores the actual position (index) of the element in the final sorted output.
4. **Build the Output:** Iterate through the input array (ideally in reverse to maintain stability), place each element into its correct position in the output array using the `count` array, and decrement the corresponding count.
---
## Code Example: Sorting a Character Array
Below is a Python implementation of Counting Sort. In this example, we sort a string (character array) by leveraging the ASCII values of the characters (ranging from 0 to 255).
```python
def countSort(arr):
# The output character array that will contain the sorted characters
output = [0 for i in range(256)]
# Create a count array to store the frequency of each character.
# Initialize all values in the count array to 0.
count = [0 for i in range(256)]
# The final list that will hold the sorted characters
ans =
# Step 1: Store the count of each character in the count array
for i in arr:
count[ord(i)] += 1
# Step 2: Update the count array so that count contains the actual
# position of this character in the output array
for i in range(256):
count += count
# Step 3: Build the output character array
for i in range(len(arr)):
output[count[ord(arr)] - 1] = arr
count[ord(arr)] -= 1
# Copy the sorted elements back to the final answer list
for i in range(len(arr)):
ans = output
return ans
# Test the implementation
arr = "wwwrunoobcom"
ans = countSort(arr)
print("Sorted character array: %s" % ("".join(ans)))
```
### Output
```text
Sorted character array: bcmnoooruwww
```
---
## Complexity Analysis
### Time Complexity
* **Best, Average, and Worst Case:** $\mathcal{O}(n + k)$, where $n$ is the number of elements in the input array and $k$ is the range of the input data (the size of the count array).
* If $k$ is $\mathcal{O}(n)$, Counting Sort runs in linear time, making it significantly faster than comparison-based algorithms which have a lower bound of $\mathcal{O}(n \log n)$.
### Space Complexity
* **Space Complexity:** $\mathcal{O}(n + k)$. It requires extra space for the `count` array of size $k$ and the `output` array of size $n$.
---
## Considerations and Limitations
While Counting Sort is highly efficient under the right conditions, it has specific limitations:
1. **Integer-Based Keys:** It can only sort integers or data types that can be mapped directly to integers (like characters or keys). It cannot easily sort floating-point numbers.
2. **Range Sensitivity ($k$):** It is only efficient when the range of input data ($k$) is not significantly larger than the number of elements ($n$). For example, sorting an array of 10 elements with values ranging from 1 to 1,000,000 would require an auxiliary array of size 1,000,000, which is highly inefficient in terms of memory.
3. **Stability:** The algorithm implemented above is **stable**, meaning that elements with equal values maintain their relative order in the sorted output. This is a crucial property when sorting complex structures or objects.