| TOPIC: Counting Sort | |
| DEFINITION: Counting sort is a stable sorting algorithm that works by counting the occurrences of each unique element in the input array and then using these counts to determine the position of each element in the sorted output. This algorithm is particularly useful for sorting integers or other discrete data within a known range. It solves the problem of efficiently sorting small integers or categorical data. | |
| TIME_COMPLEXITY: The time complexity of counting sort is O(n + k), where n is the number of elements in the input array and k is the range of input values. This is because the algorithm iterates over the input array to count the occurrences of each element and then iterates over the range of input values to construct the sorted output. | |
| SPACE_COMPLEXITY: The space complexity of counting sort is O(n + k), as the algorithm needs to store the counts of each unique element and the sorted output. | |
| USE_WHEN: Counting sort is the right tool when the input data consists of small integers or categorical data with a limited range, and memory is not a concern. It is particularly useful in scenarios where the range of input values is not significantly larger than the number of elements in the input array. | |
| AVOID_WHEN: Counting sort is a poor choice when the range of input values is very large compared to the number of elements in the input array, as this can lead to high memory usage and slow performance; in such cases, other sorting algorithms like quicksort or mergesort may be more suitable. | |
| EXAMPLE: | |
| Input: [4, 2, 2, 8, 3, 3, 1] | |
| Counting array: [0, 1, 2, 2, 1, 0, 0, 0, 1] (counts of each element from 1 to 8) | |
| Output: | |
| [1] (from count of 1) | |
| [2, 2] (from count of 2) | |
| [3, 3] (from count of 3) | |
| [4] (from count of 4) | |
| [8] (from count of 1) | |
| Result: [1, 2, 2, 3, 3, 4, 8] | |
| REAL_WORLD_ANALOGY: Counting sort is similar to organizing a collection of books by genre, where you first count how many books belong to each genre and then use these counts to arrange the books on shelves according to their genres. | |
| SOURCE_NOTE: Concepts referenced from general knowledge of sorting algorithms and data structures. |