Counting Sort is a simple but powerful sorting algorithm that works best when you have a small range of numbers. Unlike comparison-based sorting methods like bubble sort or quick sort, Counting Sort doesn’t compare elements directly. Instead, it counts how many times each value appears in the array and then calculates the correct positions of the numbers. This makes it very fast for certain types of data, especially integers or small-range datasets.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners in Perl, Counting Sort is a great way to understand how algorithms can use patterns in data to sort efficiently. It is widely used in applications like organizing scores, sorting small numbers in games, or handling discrete datasets. In this article, we will explore several Perl programs demonstrating Counting Sort in different ways, making it easy for beginners to learn and experiment.
Program 1: Basic Counting Sort with predefined integers
This first program demonstrates the classic approach to Counting Sort in Perl using a simple array of positive integers. It counts occurrences and then reconstructs the sorted array.
use strict;
use warnings;
my @arr = (4, 2, 2, 8, 3, 3, 1);
my $max = (sort { $b <=> $a } @arr)[0]; # Find the maximum value
my @count = (0) x ($max + 1);
# Count occurrences
$count[$_]++ for @arr;
# Reconstruct sorted array
my @sorted = ();
for my $i (0 .. $max) {
push @sorted, ($i) x $count[$i];
}
print "Sorted array: @sorted\n";This program works by first creating a “count array” that tracks how many times each number appears. Then, it rebuilds the array in order by repeating each number according to its count. Beginners can see that Counting Sort avoids comparisons and uses simple math to sort data quickly.
Program 2: Counting Sort using loops for clarity
This version breaks the algorithm into loops for counting, accumulation, and placement. It is slightly longer but easier for beginners to follow.
use strict;
use warnings;
my @arr = (5, 1, 3, 4, 2, 1, 3);
my $max = (sort { $b <=> $a } @arr)[0];
my @count = (0) x ($max + 1);
# Counting occurrences
for my $num (@arr) {
$count[$num]++;
}
# Build the sorted array
my @sorted = ();
for my $i (0 .. $max) {
for (1 .. $count[$i]) {
push @sorted, $i;
}
}
print "Sorted array: @sorted\n";By explicitly using loops for each step, beginners can visualize how Counting Sort transforms the original array into a sorted one. The approach emphasizes clarity and understanding over compact code.
Program 3: Counting Sort with negative numbers handled
By default, Counting Sort works only with non-negative integers. This program adjusts the algorithm to handle negative numbers by offsetting them to a positive range.
use strict;
use warnings;
my @arr = (-5, 3, 0, -2, 4, -1, 3);
my $min = (sort { $a <=> $b } @arr)[0];
my $max = (sort { $b <=> $a } @arr)[0];
my @count = (0) x ($max - $min + 1);
# Counting with offset
for my $num (@arr) {
$count[$num - $min]++;
}
# Reconstruct sorted array
my @sorted = ();
for my $i (0 .. $#count) {
push @sorted, ($i + $min) x $count[$i];
}
print "Sorted array: @sorted\n";Here, the key idea is adding an offset to all numbers so that negative numbers become positive indices in the count array. Beginners can see how minor adjustments make the algorithm more flexible for real-world datasets.
Program 4: Counting Sort for larger numbers using hash
When the range of numbers is too large for a fixed-size array, using a hash allows counting without wasting memory. This example demonstrates that.
use strict;
use warnings;
my @arr = (100, 5, 50, 5, 20, 100, 1);
my %count;
# Counting occurrences using hash
$count{$_}++ for @arr;
# Build sorted array by keys
my @sorted = ();
for my $key (sort { $a <=> $b } keys %count) {
push @sorted, ($key) x $count{$key};
}
print "Sorted array: @sorted\n";This method is useful for beginners to understand that Counting Sort can be adapted to handle sparse or large numbers efficiently. Hashes store only the values that exist, which saves memory compared to a giant array.
Program 5: Counting Sort for floating-point numbers
Counting Sort traditionally works with integers, but it can handle floating-point numbers by scaling them to integers. This example shows a simple approach.
use strict;
use warnings;
my @arr = (2.5, 3.2, 1.1, 2.5, 0.5);
my $scale = 10; # Multiply by 10 to make integers
my @scaled = map { int($_ * $scale) } @arr;
my $max = (sort { $b <=> $a } @scaled)[0];
my @count = (0) x ($max + 1);
# Counting occurrences
$count[$_]++ for @scaled;
# Reconstruct sorted array
my @sorted = ();
for my $i (0 .. $max) {
push @sorted, ($i / $scale) x $count[$i];
}
print "Sorted array: @sorted\n";By multiplying floating numbers by a scale factor, they become integers that can be counted. This technique shows beginners that Counting Sort can be adapted for different types of numeric data with simple math.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Counting Sort in Perl.
Q1. Why is Counting Sort faster than comparison-based sorts?
Counting Sort avoids comparisons and works by counting occurrences, which makes it O(n + k) in time, faster than O(n log n) for small ranges.
Q2. Can Counting Sort handle negative numbers?
Yes, with a small adjustment to offset negative numbers into positive indices.
Q3. Can Counting Sort be used for floating-point numbers?
Yes, by scaling the numbers into integers before counting.
Q4. When should I avoid Counting Sort?
It is not suitable for very large ranges of numbers with lots of empty spots, as it may waste memory or be inefficient.
Q5. Is Counting Sort stable?
Yes, it preserves the order of equal elements when implemented correctly.
Conclusion
Counting Sort is a practical algorithm for beginners to learn, offering a new perspective on sorting without comparisons. By counting occurrences and rebuilding the array, it can sort integers quickly and can be adapted for negative or floating-point numbers. The programs in this article illustrate different ways to implement Counting Sort in Perl, from simple integer arrays to more advanced scenarios.
Running these programs, experimenting with the data, and trying slight modifications will help beginners gain confidence in understanding Counting Sort and algorithm design in general. With practice, you can see how even simple ideas can become powerful tools for sorting in real-world applications.
