Counting Sort is a simple yet very efficient sorting algorithm, especially for integers or data that falls within a known range. Unlike comparison-based sorts like Quick Sort or Merge Sort, Counting Sort works by counting the occurrences of each value and then using these counts to place elements in their correct positions. This makes it extremely fast for certain types of data, with a time complexity that can be linear, which is impressive for beginners to see in action.
This algorithm is widely used in situations where you have integer data or small ranges, like sorting ages, test scores, or other categorical numbers. For beginners learning R programming, Counting Sort is an excellent example of how understanding the properties of your data can lead to faster algorithms. It also introduces the idea of non-comparison sorting, which is a different mindset from the traditional bubble or insertion sorts.
Program 1: Basic Counting Sort for positive integers
This program shows a straightforward implementation of Counting Sort for a simple array of positive integers. It is designed for clarity so beginners can run it and understand each step.
counting_sort <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
data <- c(4, 2, 2, 8, 3, 3, 1)
print(counting_sort(data))This program counts each element in the array and then reconstructs the sorted array using these counts. Beginners can see that Counting Sort avoids direct comparisons, which is a unique and efficient approach.
Program 2: Counting Sort using a helper function
This version separates the counting logic into a helper function, making the program more modular and easier to read.
count_elements <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
return(count)
}
counting_sort_helper <- function(arr) {
count <- count_elements(arr)
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
data <- c(5, 3, 0, 2, 3, 1)
print(counting_sort_helper(data))This style teaches beginners how breaking a program into smaller parts can make it easier to understand and maintain, which is a useful skill for all programming.
Program 3: Counting Sort with input validation
This version adds a simple check to ensure that the array contains only non-negative integers. This is helpful for beginners learning to write robust code.
counting_sort <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
counting_sort_safe <- function(arr) {
if (!all(arr >= 0)) {
stop("Counting Sort only supports non-negative integers")
}
return(counting_sort(arr))
}
data <- c(2, 5, 3, 0, 2)
print(counting_sort_safe(data))This version emphasizes the importance of validating input to prevent errors or unexpected results. Beginners learn that safe programming is as important as correct logic.
Program 4: Counting Sort with frequency table printout
This program prints the frequency table, so learners can see exactly how the algorithm counts each number before creating the sorted array.
counting_sort_verbose <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
print(paste("Frequency table:", paste(count, collapse = " ")))
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
data <- c(1, 4, 1, 2, 7, 5)
print(counting_sort_verbose(data))This program helps beginners understand the mechanics of Counting Sort by showing exactly how the counts are stored and used to sort the array.
Program 5: Counting Sort using while loops
This version replaces for loops with while loops for practice with different loop styles in R.
counting_sort_while <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
i <- 1
while (i <= length(arr)) {
count[arr[i] + 1] <- count[arr[i] + 1] + 1
i <- i + 1
}
sorted_arr <- integer(length(arr))
index <- 1
i <- 1
while (i <= length(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
i <- i + 1
}
return(sorted_arr)
}
data <- c(4, 2, 4, 3, 1)
print(counting_sort_while(data))This variation reinforces beginners’ understanding of loops while keeping the counting logic intact. It also shows that there are multiple ways to implement the same algorithm.
Program 6: Counting Sort with helper function and while loops
This program combines helper functions and while loops to demonstrate flexible programming styles.
count_elements_while <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
i <- 1
while (i <= length(arr)) {
count[arr[i] + 1] <- count[arr[i] + 1] + 1
i <- i + 1
}
return(count)
}
counting_sort_while_helper <- function(arr) {
count <- count_elements_while(arr)
sorted_arr <- integer(length(arr))
index <- 1
i <- 1
while (i <= length(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
i <- i + 1
}
return(sorted_arr)
}
data <- c(6, 3, 4, 1, 3)
print(counting_sort_while_helper(data))Beginners can see how combining techniques—helper functions and loop variations—does not change the algorithm’s correctness but can improve clarity.
Program 7: Counting Sort optimized for repeated numbers
This example emphasizes Counting Sort’s efficiency when the array contains many repeated numbers.
counting_sort <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
data <- c(2, 3, 2, 3, 2, 3, 1, 1, 1)
print(counting_sort(data))The program runs very efficiently in this case, showing beginners why Counting Sort is ideal for datasets with limited ranges and frequent duplicates.
Program 8: Counting Sort for small datasets
Counting Sort also works perfectly for very small datasets, giving beginners quick, visible results.
counting_sort <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
data <- c(1, 0, 3, 2)
print(counting_sort(data))Small datasets help beginners trace each step and understand how the algorithm uses counting to sort values.
Program 9: Counting Sort for negative and floating-point numbers
Counting Sort by default works only with non-negative integers. For negative numbers or decimals, we can adjust the algorithm by shifting and scaling values.
counting_sort <- function(arr) {
max_val <- max(arr)
count <- integer(max_val + 1)
for (num in arr) {
count[num + 1] <- count[num + 1] + 1
}
sorted_arr <- integer(length(arr))
index <- 1
for (i in seq_along(count)) {
while (count[i] > 0) {
sorted_arr[index] <- i - 1
index <- index + 1
count[i] <- count[i] - 1
}
}
return(sorted_arr)
}
counting_sort_extended <- function(arr) {
shift <- abs(min(arr))
scaled_arr <- round(arr + shift) # shift negative numbers to positive integers
sorted_scaled <- counting_sort(scaled_arr)
return(sorted_scaled - shift)
}
data <- c(-3, -1, 0, 2, 1)
print(counting_sort_extended(data))This adjustment shows beginners how to extend a basic algorithm to handle more complex real-world data.
Frequently Asked Questions (FAQ)
This section answers common questions about Counting Sort in R in a beginner-friendly way.
Q1. Can Counting Sort handle negative numbers?
By default, no, but you can shift the data so all values are non-negative, as shown in Program 9.
Q2. Is Counting Sort fast for large datasets?
It is very fast for integers with a limited range, but less suitable for very large ranges with many unique values.
Q3. Why is Counting Sort not comparison-based?
Counting Sort does not compare elements directly; it counts occurrences and reconstructs the sorted array.
Q4. Can Counting Sort handle decimals?
Decimals need to be scaled or rounded to integers before using Counting Sort.
Conclusion
Counting Sort is an elegant and efficient algorithm for sorting integers and categorical numbers. By exploring different R programs, beginners can see how variations in loops, helper functions, and input handling all affect implementation and understanding.
Practicing these examples helps beginners understand how Counting Sort works and teaches important programming habits, such as modular code and input validation. With this knowledge, you can confidently apply Counting Sort to real datasets and expand your understanding of sorting algorithms in R.
