Sorting is a fundamental concept in programming, and mastering different algorithms helps you write efficient and optimized code. Counting Sort is a non-comparison-based sorting algorithm that works best with integers within a specific range. Unlike Quick Sort or Merge Sort, it counts the occurrence of each element and calculates their positions, making it extremely fast for certain datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is widely used in scenarios where speed is critical and the range of elements is known, such as sorting exam scores, small-range IDs, or frequency-based data. For beginners, it provides a clear example of how array manipulation and counting can solve a sorting problem efficiently, without relying on traditional comparisons.
Program 1: Basic Counting Sort Using Loops
This first program demonstrates the standard way to perform Counting Sort using simple loops. It is straightforward and perfect for beginners who are learning sorting algorithms for the first time.
void countingSort(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
List<int> count = List.filled(max + 1, 0);
for (int num in arr) {
count[num]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
void main() {
List<int> numbers = [4, 2, 2, 8, 3, 3, 1];
print("Original List: $numbers");
countingSort(numbers);
print("Sorted List: $numbers");
}In this program, we first find the largest number in the list and create a counting array to store the frequency of each number. Then, we rebuild the original array in sorted order using the counts. This method is simple to understand and very efficient for numbers in a small range. Beginners can easily visualize how counting and placing elements leads to a sorted list.
Program 2: Counting Sort With a Separate Output Array
Here, we improve the previous program by using a separate output array. This approach ensures the original array is untouched until the sorting is complete, making it easier to handle and debug.
void countingSortWithOutput(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
List<int> count = List.filled(max + 1, 0);
List<int> output = List.filled(arr.length, 0);
for (int num in arr) {
count[num]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
void main() {
List<int> numbers = [4, 2, 2, 8, 3, 3, 1];
print("Original List: $numbers");
countingSortWithOutput(numbers);
print("Sorted List: $numbers");
}Using a separate output array can prevent overwriting data during sorting. This method also introduces beginners to the idea of cumulative counts, which is fundamental for understanding more advanced sorting techniques like Radix Sort. It’s especially useful when the original order of elements needs to be preserved.
Program 3: Counting Sort Using Recursion
Recursion is a powerful concept in programming, and Counting Sort can also be implemented recursively. This program shows a beginner-friendly way to integrate recursion with counting logic.
void countingSortRecursive(List<int> arr, int max) {
List<int> count = List.filled(max + 1, 0);
for (int num in arr) {
count[num]++;
}
int index = 0;
void placeElements(int i) {
if (i >= count.length) return;
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
placeElements(i + 1);
}
placeElements(0);
}
void main() {
List<int> numbers = [4, 2, 2, 8, 3, 3, 1];
print("Original List: $numbers");
countingSortRecursive(numbers, numbers.reduce((a, b) => a > b ? a : b));
print("Sorted List: $numbers");
}In this program, recursion helps loop through the counting array instead of using traditional loops. Beginners can see how recursive calls replace iterative loops, making it an interesting exercise to understand both recursion and counting logic. This method also lays the foundation for recursive thinking in other algorithms.
Program 4: Counting Sort With Negative Numbers
By default, Counting Sort works with positive numbers, but it can be adapted for lists containing negative values. This program demonstrates that adaptation.
void countingSortWithNegatives(List<int> arr) {
int min = arr.reduce((a, b) => a < b ? a : b);
int max = arr.reduce((a, b) => a > b ? a : b);
List<int> count = List.filled(max - min + 1, 0);
for (int num in arr) {
count[num - min]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
void main() {
List<int> numbers = [4, -2, 2, 8, -3, 3, 1];
print("Original List: $numbers");
countingSortWithNegatives(numbers);
print("Sorted List: $numbers");
}This adaptation works by shifting all numbers so that the minimum number becomes zero. This is helpful for beginners who may encounter datasets containing negative numbers. Understanding this technique expands the practical use of Counting Sort in real-world scenarios.
Program 5: Counting Sort with Stability
In this program, Counting Sort is implemented to maintain stability, meaning the relative order of equal elements is preserved.
void stableCountingSort(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
List<int> count = List.filled(max + 1, 0);
for (int num in arr) count[num]++;
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
List<int> output = List.filled(arr.length, 0);
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
void main() {
List<int> arr = [4, 2, 2, 8, 3, 3, 1];
print('Original Array: $arr');
stableCountingSort(arr);
print('Sorted Array: $arr');
}This program demonstrates the stable version of Counting Sort, which is important when sorting data with multiple attributes. Beginners can see how using an output array preserves the order of duplicates.
Program 6: Stable Counting Sort for Strings
Counting Sort can also be applied to strings or characters. This program sorts a string alphabetically while preserving character order.
void countingSortString(String str) {
List<int> count = List.filled(256, 0);
List<String> output = List.filled(str.length, '');
for (int i = 0; i < str.length; i++) {
count[str.codeUnitAt(i)]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = str.length - 1; i >= 0; i--) {
output[count[str.codeUnitAt(i)] - 1] = str[i];
count[str.codeUnitAt(i)]--;
}
print(output.join());
}
void main() {
String text = "dartprogram";
print("Original String: $text");
print("Sorted String: ");
countingSortString(text);
}Here, Counting Sort handles strings by using the ASCII values of characters. Beginners can see how the same principle applies beyond numbers, making the algorithm versatile. This approach is especially useful when sorting large strings or character datasets efficiently.
Program 7: Counting Sort for Large Range
Sometimes the range of elements is large. This program shows a way to manage larger datasets efficiently by minimizing memory usage.
void countingSortLargeRange(List<int> arr) {
int min = arr.reduce((a, b) => a < b ? a : b);
int max = arr.reduce((a, b) => a > b ? a : b);
Map<int, int> count = {};
for (int num in arr) {
count[num] = (count[num] ?? 0) + 1;
}
int index = 0;
for (int num = min; num <= max; num++) {
while ((count[num] ?? 0) > 0) {
arr[index++] = num;
count[num] = count[num]! - 1;
}
}
}
void main() {
List<int> arr = [1000, 2, 5000, 1, 2, 1000];
print('Original Array: $arr');
countingSortLargeRange(arr);
print('Sorted Array: $arr');
}This version introduces the use of a map instead of a large array to store counts. Beginners can learn how to handle sparse or large ranges without excessive memory usage.
Program 8: Counting Sort with Frequency Display
Here, Counting Sort is extended to display the frequency of each element alongside sorting.
void countingSortWithFrequency(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
List<int> count = List.filled(max + 1, 0);
for (int num in arr) count[num]++;
print('Element Frequencies:');
for (int i = 0; i <= max; i++) {
if (count[i] > 0) print('$i occurs ${count[i]} times');
}
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
void main() {
List<int> arr = [4, 2, 2, 8, 3, 3, 1];
print('Original Array: $arr');
countingSortWithFrequency(arr);
print('Sorted Array: $arr');
}This program shows the power of Counting Sort beyond just sorting. Beginners can learn how counting elements can also help analyze data distributions.
Frequently Asked Questions (FAQ)
Counting Sort is simple but often raises beginner questions.
Q1: What is the time complexity of Counting Sort?
It is O(n + k), where n is the number of elements and k is the range of input values.
Q2: Is Counting Sort stable?
Yes, with a proper implementation using an output array, it preserves the order of equal elements.
Q3: Can Counting Sort handle negative numbers?
Yes, but indices must be offset to handle negative values.
Q4: When is Counting Sort most useful?
It is ideal for integers or small-range data where comparisons are unnecessary, like exam scores or frequency counts.
Q5: Can Counting Sort handle floating-point numbers?
Not directly, because it relies on integer indexing. You would need to map floats to integers first.
Conclusion
Counting Sort is a simple yet powerful sorting algorithm, perfect for beginners who want to understand efficient sorting techniques. Through these examples in Dart, we have explored basic loops, recursion, handling negative numbers, and even sorting strings. Each version of Counting Sort shows a different way to solve the same problem, helping beginners build a deeper understanding of algorithms.
By practicing these programs, you can strengthen your Dart programming skills and improve your problem-solving abilities. Counting Sort is a great starting point, and mastering it will make learning more advanced sorting techniques much easier. So grab your keyboard, try these examples, and start experimenting with your own data!
