Sorting is a key concept in programming, helping us organize data efficiently. Whether you are working with numbers, scores, or small datasets, sorting algorithms play a crucial role in making your programs faster and more readable. Counting Sort is a simple yet effective algorithm that is ideal for sorting integers within a known range. Unlike other comparison-based sorting methods, Counting Sort counts the occurrences of each element and then calculates their positions in the sorted array, making it extremely fast for specific use cases.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is particularly useful when you have datasets where numbers fall within a limited range. You will often see it applied in areas like student scores, frequency counts, and situations where the maximum value in the dataset is not too large. For beginners, Counting Sort is an excellent way to understand how clever use of arrays and counting can replace repeated comparisons, offering both efficiency and simplicity.
Program 1: Basic Counting Sort Using Loops
This program demonstrates a straightforward Counting Sort that sorts a predefined array of positive integers in ascending order.
<?php
$array = [4, 2, 2, 8, 3, 3, 1];
$max = max($array);
$count = array_fill(0, $max + 1, 0);
foreach ($array as $num) {
$count[$num]++;
}
$sortedArray = [];
for ($i = 0; $i <= $max; $i++) {
while ($count[$i] > 0) {
$sortedArray[] = $i;
$count[$i]--;
}
}
echo "Sorted Array: ";
print_r($sortedArray);
?>This program works by first counting how many times each number appears in the array. Then, it reconstructs the array in sorted order by repeating each number according to its count. Beginners can easily see how counting provides a direct path to sorting without complex comparisons, making the algorithm efficient for small-range numbers.
Program 2: Counting Sort as a Reusable Function
Here, we wrap Counting Sort in a function to make it reusable and modular. This allows you to sort any array of integers by simply calling the function.
<?php
function countingSort($arr) {
$max = max($arr);
$count = array_fill(0, $max + 1, 0);
foreach ($arr as $num) {
$count[$num]++;
}
$sortedArray = [];
for ($i = 0; $i <= $max; $i++) {
while ($count[$i] > 0) {
$sortedArray[] = $i;
$count[$i]--;
}
}
return $sortedArray;
}
$array = [5, 1, 3, 4, 2, 3, 1];
$sorted = countingSort($array);
echo "Sorted Array using Function: ";
print_r($sorted);
?>By using a function, you can apply Counting Sort to multiple arrays without rewriting the code. Beginners can learn the value of modular design while understanding the counting logic in a clear and structured way.
Program 3: Counting Sort for Descending Order
This program shows how to modify Counting Sort to sort elements in descending order instead of ascending.
<?php
$array = [4, 2, 2, 8, 3, 3, 1];
$max = max($array);
$count = array_fill(0, $max + 1, 0);
foreach ($array as $num) {
$count[$num]++;
}
$sortedArray = [];
for ($i = $max; $i >= 0; $i--) {
while ($count[$i] > 0) {
$sortedArray[] = $i;
$count[$i]--;
}
}
echo "Descending Sorted Array: ";
print_r($sortedArray);
?>By simply reversing the order of iteration, the array is sorted from largest to smallest. Beginners can easily grasp how a small change in logic can reverse the sorting order, demonstrating Counting Sort’s flexibility for practical scenarios like ranking scores or prioritizing items.
Program 4: Counting Sort With Negative Numbers
Counting Sort traditionally handles positive integers, but it can be adapted for negative numbers by shifting the values. This program demonstrates that approach.
<?php
$array = [4, -2, 2, -8, 3, 0, -1];
$min = min($array);
$max = max($array);
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
foreach ($array as $num) {
$count[$num - $min]++;
}
$sortedArray = [];
for ($i = 0; $i < $range; $i++) {
while ($count[$i] > 0) {
$sortedArray[] = $i + $min;
$count[$i]--;
}
}
echo "Sorted Array with Negative Numbers: ";
print_r($sortedArray);
?>This program shifts all values so that the smallest number starts at zero. Beginners can learn how Counting Sort can be adapted for real-world data that includes negative numbers. It emphasizes problem-solving by adjusting array indexing for counting purposes.
Program 5: Counting Sort Using Recursion
Although Counting Sort is usually iterative, recursion can be introduced to process each value in the count array. This example shows a recursive reconstruction of the sorted array.
<?php
function recursiveCountingSort($count, $index = 0, &$sortedArray = []) {
if ($index >= count($count)) return;
while ($count[$index] > 0) {
$sortedArray[] = $index;
$count[$index]--;
}
recursiveCountingSort($count, $index + 1, $sortedArray);
}
$array = [5, 2, 4, 2, 1, 3, 1];
$max = max($array);
$count = array_fill(0, $max + 1, 0);
foreach ($array as $num) $count[$num]++;
$sortedArray = [];
recursiveCountingSort($count, 0, $sortedArray);
echo "Sorted Array using Recursion: ";
print_r($sortedArray);
?>This recursive approach allows beginners to explore recursion in a practical context. It shows that even a counting algorithm can be adapted with recursion, helping learners develop a deeper understanding of algorithmic thinking.
Frequently Asked Questions (FAQ)
Counting Sort is simple yet powerful, and beginners often have questions about its use and limitations.
Q1: When should I use Counting Sort?
Counting Sort works best for integers with a small range. It is faster than comparison-based algorithms for such data but not suitable for large ranges or floating-point numbers.
Q2: Can Counting Sort handle negative numbers?
Yes, by shifting all values so that the minimum number becomes zero, negative numbers can be sorted effectively.
Q3: Is Counting Sort stable?
Yes, Counting Sort is stable, meaning equal elements preserve their original order in the sorted array.
Q4: Can Counting Sort sort strings or characters?
It can, by treating characters as their ASCII values. However, it is most efficient for numbers.
Q5: Why is Counting Sort faster than Bubble Sort or Insertion Sort?
Counting Sort avoids repeated comparisons and directly counts occurrences, making it very efficient for small-range datasets.
Conclusion
Counting Sort is a beginner-friendly algorithm that combines simplicity with efficiency. By counting occurrences and reconstructing the array, it provides a fast way to sort integers, including negative numbers, and can be adapted for descending order or recursive processing. These PHP examples demonstrate the versatility and practical applications of Counting Sort. Practicing these programs helps beginners build a strong foundation in sorting algorithms and prepares them for more advanced data handling in PHP.
![C++ Operator Overloading: The Subscript Operator ([])](https://coderscratchpad.com/wp-content/uploads/2024/05/Wordpress-blog-1200-x-600-px-17-1-1024x512.webp)
