Counting Sort — 5 Row Visualizer (Single digit 0–9)
What is Counting Sort?
Counting Sort is a non-comparison-based integer sorting algorithm used mainly as a sub-method in Radix Sort. Instead of comparing elements, it counts how many times each value appears in the array and uses that information to determine their final positions. The key idea is simple: If you know how many numbers in the array are smaller than or equal to a given number, you can directly place that number in its correct position. For example, if the number x = 5 and there are 4 numbers ≤ 5, then 5 will be placed at position 4. The algorithm works in three main steps: 1. Count how many times each number occurs. 2. Compute cumulative counts to know how many numbers are smaller or equal to each value. 3. Place each element into its correct position using those cumulative counts. Counting Sort runs in approximately 3N time — N for counting, N for cumulative computation, and N for placing elements — making its overall time complexity O(n + k), where n is the number of elements and k is the range of input values (0–9 for single-digit numbers). -------------------------------------------- Example 1: 4 Numbers Input: [4, 2, 1, 3] Step 1: Count → 1:1, 2:1, 3:1, 4:1 Step 2: Cumulative → 1:1, 2:2, 3:3, 4:4 Step 3: Place → [1, 2, 3, 4] Output: [1, 2, 3, 4] -------------------------------------------- Example 2: 2 Numbers Input: [7, 2] Step 1: Count → 2:1, 7:1 Step 2: Cumulative → 2:1, 7:2 Step 3: Place → [2, 7] Output: [2, 7] -------------------------------------------- Example 3: 11 Numbers Input: [4, 2, 9, 1, 3, 1, 0, 8, 5, 9, 2] Step 1: Count → 0:1, 1:2, 2:2, 3:1, 4:1, 5:1, 8:1, 9:2 Step 2: Cumulative → 0:1, 1:3, 2:5, 3:6, 4:7, 5:8, 8:9, 9:11 Step 3: Place → [0, 1, 1, 2, 2, 3, 4, 5, 8, 9, 9] Output: [0, 1, 1, 2, 2, 3, 4, 5, 8, 9, 9] -------------------------------------------- These examples show how Counting Sort arranges data without comparisons, making it especially efficient for small integer ranges and useful as a sub-step in Radix Sort.
0 Comments