Sorting is one of the most important skills in programming because it allows us to organize data efficiently. Among the various sorting algorithms, Counting Sort stands out because it works differently from comparison-based sorts like Bubble Sort or Quick Sort. Instead of comparing elements, Counting Sort counts the occurrences of each number in the dataset and then calculates their positions in the sorted array. This makes it extremely fast for datasets where the numbers are within a known, limited range.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is particularly useful in scenarios like grading systems, frequency analysis, or any situation where you need to sort integers quickly without complex comparisons. It is a stable and simple algorithm that introduces beginners to the idea of counting occurrences and using auxiliary arrays to sort data efficiently. In this article, we will explore multiple ways to implement Counting Sort in Ruby, including standard iterative approaches, optimized versions, and handling different types of data.
Program 1: Basic Counting Sort for Positive Integers
This first program demonstrates a simple Counting Sort for a predefined array of positive integers.
# Program 1: Basic Counting Sort
def counting_sort(array)
max_val = array.max
count = Array.new(max_val + 1, 0)
sorted_array = []
array.each { |num| count[num] += 1 }
count.each_with_index do |c, num|
c.times { sorted_array << num }
end
sorted_array
end
numbers = [4, 2, 2, 8, 3, 3, 1]
sorted_array = counting_sort(numbers)
puts "Sorted array: #{sorted_array}"In this program, we first create a count array to store the frequency of each element. Then, we iterate through the count array to reconstruct the sorted array. Beginners can see that Counting Sort avoids comparisons entirely, making it very efficient for small ranges of numbers.
Program 2: Counting Sort with Zero-Based Indexing
Counting Sort can also be implemented using zero-based indexing to handle arrays more efficiently. This approach emphasizes clarity and indexing logic.
# Program 2: Counting Sort with zero-based indexing
def counting_sort_zero(array)
max_val = array.max
count = Array.new(max_val + 1, 0)
array.each { |num| count[num] += 1 }
index = 0
(0..max_val).each do |num|
count[num].times do
array[index] = num
index += 1
end
end
array
end
numbers = [5, 2, 9, 5, 2, 3]
sorted_array = counting_sort_zero(numbers)
puts "Sorted array: #{sorted_array}"Here, the sorted array is constructed directly in the original array by iterating through the count array. Beginners can understand how Counting Sort efficiently places each element without extra comparisons.
Program 3: Counting Sort for Negative and Positive Integers
Counting Sort can be extended to handle arrays containing both negative and positive integers by offsetting the index.
# Program 3: Counting Sort for negative and positive numbers
def counting_sort_with_negatives(array)
min_val = array.min
max_val = array.max
range = max_val - min_val + 1
count = Array.new(range, 0)
sorted_array = []
array.each { |num| count[num - min_val] += 1 }
count.each_with_index do |c, i|
c.times { sorted_array << i + min_val }
end
sorted_array
end
numbers = [-5, -10, 0, -3, 8, 5, -1, 10]
sorted_array = counting_sort_with_negatives(numbers)
puts "Sorted array with negatives: #{sorted_array}"In this approach, an offset is applied so that negative numbers map correctly into the count array. Beginners can see how Counting Sort can be adapted for different types of integer datasets while keeping the logic straightforward.
Program 4: Optimized Counting Sort with Prefix Sum
An optimized version of Counting Sort uses a prefix sum to place elements directly into the correct position, maintaining stability.
# Program 4: Optimized Counting Sort using prefix sum
def counting_sort_optimized(array)
max_val = array.max
count = Array.new(max_val + 1, 0)
output = Array.new(array.length)
array.each { |num| count[num] += 1 }
(1..max_val).each { |i| count[i] += count[i - 1] }
(array.length - 1).downto(0) do |i|
num = array[i]
output[count[num] - 1] = num
count[num] -= 1
end
output
end
numbers = [4, 2, 2, 8, 3, 3, 1]
sorted_array = counting_sort_optimized(numbers)
puts "Optimized sorted array: #{sorted_array}"This version calculates the position of each element using a prefix sum array, which ensures that the sort is stable and elements appear in the same order as in the original array when equal. Beginners can understand that this method improves Counting Sort for real-world usage, particularly when stability matters.
Frequently Asked Questions (FAQ)
Counting Sort often raises questions for beginners. Here are some common ones:
Q1: What is the time complexity of Counting Sort?
Counting Sort has a time complexity of O(n + k), where n is the number of elements and k is the range of the input. This makes it very efficient for small ranges.
Q2: Is Counting Sort stable?
Yes, with the prefix sum approach, Counting Sort is stable, meaning equal elements retain their relative order.
Q3: Can Counting Sort handle negative numbers?
Yes, by applying an offset to the indices in the count array, negative numbers can be sorted easily.
Q4: When should I use Counting Sort?
Counting Sort is best for integer datasets with a limited range of values, especially when speed and stability are important.
Q5: Can Counting Sort handle floating-point numbers?
Counting Sort is generally not suitable for floating-point numbers because it relies on integer indexing.
Conclusion
In this article, we explored multiple ways to implement Counting Sort in Ruby, including basic sorting for positive integers, handling negative numbers, and an optimized stable version using prefix sums. Counting Sort is a simple yet powerful algorithm that avoids comparisons and leverages counting logic, making it extremely efficient for integer datasets with a limited range. By practicing these examples, beginners can understand how to adapt Counting Sort for different types of data, how to maintain stability, and how to optimize performance. It’s a great tool to have in your Ruby programming toolkit for fast and reliable sorting.
