concept · INFO-CS-ADS-136Counting Sort
Counting Sort is a non-comparison-based sorting algorithm that counts how many times each value occurs and uses those counts to construct a sorted output. It is especially efficient when the range of integer keys is relatively small.
Explanation
Overview
Counting Sort is a sorting algorithm that organizes elements by counting the frequency of each possible key value instead of comparing elements directly with one another.
Purpose
Its purpose is to sort suitable integer or discrete-key datasets efficiently when the range of possible values is manageable relative to the number of elements.
Working principle
The algorithm creates a counting structure for the possible key values, records how often each value appears, and then uses the frequency information to determine the sorted positions of the elements.
Key concepts
name: Core idea; description: The central focus of counting sort is the capability described here: Counting Sort is a non-comparison-based sorting algorithm that counts how many times each value occurs and uses those counts to construct a sorted output. It is especially efficient when the range of integer keys is relatively small.; name: Problem context; description: Counting Sort is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using counting sort, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
O(n + k) time, where n is the number of elements and k is the size of the key range. Counting and output construction both require processing the input or the counting structure.
Space complexity
O(n + k) auxiliary space for a common stable implementation with a count array and a separate output array. A frequency-only variant may use less memory but does not directly provide the same stability guarantee for records.
Example
For [4, 2, 4, 1, 2], the algorithm counts the occurrences of 1, 2, 3, and 4. It then reconstructs the collection as [1, 2, 2, 4, 4].
Example or application
For [4, 2, 4, 1, 2], the algorithm counts the occurrences of 1, 2, 3, and 4. It then reconstructs the collection as [1, 2, 2, 4, 4].
Definition
Counting Sort is a sorting algorithm that organizes elements by counting the frequency of each possible key value instead of comparing elements directly with one another.
Purpose
Its purpose is to sort suitable integer or discrete-key datasets efficiently when the range of possible values is manageable relative to the number of elements.
Working Principle
The algorithm creates a counting structure for the possible key values, records how often each value appears, and then uses the frequency information to determine the sorted positions of the elements.
Frequency Array
The frequency array stores the number of occurrences of each key. For example, if the input is [4, 2, 4, 1, 2], the counts indicate one occurrence of 1, two occurrences of 2, no occurrence of 3, and two occurrences of 4.
Cumulative Counts
A cumulative-count array stores running totals of the frequencies. These totals identify the final position ranges occupied by each key in the sorted output.
Algorithm Steps
Determine the minimum and maximum key values.
Allocate a counting array covering the required key range.
Count the frequency of each input value.
Convert frequencies into cumulative counts when stable output construction is required.
Place elements into their correct positions in an output array.
Return or copy the sorted output.
Pseudocode
COUNTING_SORT(A):
if A is empty:
return A
minValue = minimum(A)
maxValue = maximum(A)
count = array of zeros with size maxValue - minValue + 1
for value in A:
count[value - minValue] += 1
output = empty array
for i = 0 to length(count) - 1:
repeat count[i] times:
append i + minValue to output
return output
Time Complexity
O(n + k) time, where n is the number of elements and k is the size of the key range. Counting and output construction both require processing the input or the counting structure.
Space Complexity
O(n + k) auxiliary space for a common stable implementation with a count array and a separate output array. A frequency-only variant may use less memory but does not directly provide the same stability guarantee for records.
Best Case
O(n + k) time because the algorithm must process the input and the relevant counting range even when the input is already sorted.
Average Case
O(n + k) time when the counting range is represented efficiently and the key values fit within the allocated structure.
Worst Case
O(n + k) time for the standard implementation, assuming the counting array can be allocated and initialized successfully.
Stability
Counting Sort can be stable when cumulative counts are used to place records into the output array while processing the input in reverse order, or through another order-preserving placement method.
Non Comparison Property
Counting Sort does not determine the relative order of every pair through comparisons. It uses the key values as indexes in a counting structure.
Key Range
The key range is the difference between the maximum and minimum possible values. A large range can require excessive memory even when the input contains relatively few elements.
Negative Values
Negative integers can be handled by shifting each key by the minimum value. The counting index becomes value - minValue, allowing the counting array to begin at index zero.
Advantages
Can achieve linear time when the key range is suitably small.
Does not depend on pairwise comparisons.
Can be stable for record sorting.
Useful as a component of Radix Sort.
Efficient for bounded integer datasets.
Limitations
Requires a manageable key range.
Can consume large amounts of memory when values are widely spread.
Standard forms are not suitable for arbitrary objects without discrete keys.
Its efficiency depends on the relationship between n and k.
Comparison With Comparison Sorting
Comparison-based algorithms generally have an Ω(n log n) worst-case lower bound. Counting Sort can achieve O(n + k) because it uses assumptions about the keys rather than relying entirely on comparisons.
Practical Applications
Sorting examination scores within a fixed range.
Sorting small-range integer values.
Counting occurrences of categories or symbols.
Preparing data for Radix Sort.
Sorting records with bounded integer keys.
Common Errors
Allocating a counting array based on the number of elements instead of the key range.
Failing to account for negative values.
Using incorrect cumulative-count positions.
Processing records in the wrong direction and losing stability.
Ignoring the memory cost of a large key range.
Implementation Considerations
The algorithm should verify the key range before allocating memory. When sorting records, the cumulative-count placement method must preserve the original order of equal-key elements if stability is required.
Key Takeaway
Counting Sort replaces comparisons with frequency counting. It can be extremely efficient for small-range integer keys, but its memory usage becomes impractical when the range is very large.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of counting sort is the capability described here: Counting Sort is a non-comparison-based sorting algorithm that counts how many times each value occurs and uses those counts to construct a sorted output. It is especially efficient when the range of integer keys is relatively small. |
Problem context | Counting Sort is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using counting sort, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of counting sort? | Counting Sort is a non-comparison-based sorting algorithm that counts how many times each value occurs and uses those counts to construct a sorted output. It is especially efficient when the range of integer keys is relatively small. |
What should be checked before applying counting sort? | For counting sort, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of counting sort be validated? | Trace a representative counting sort case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of counting sort.
Identify the assumptions, inputs, and conditions relevant to counting sort.
Evaluate an application of counting sort for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures