Sorting is a fundamental part of programming because it helps us organize data efficiently. Counting Sort is a special sorting algorithm that is particularly useful when you know the range of the input numbers in advance. Unlike comparison-based sorting algorithms such as Bubble Sort or Quick Sort, Counting Sort doesn’t compare elements directly. Instead, it counts the occurrences of each value and then uses this information to build a sorted array.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is widely used in situations where the input values are integers or can be mapped to integers within a small range. For example, it is perfect for sorting exam scores, ages, or small datasets where speed is important. In F#, implementing Counting Sort gives beginners a chance to learn about arrays, loops, and counting techniques in a clear and practical way.
Program 1: Basic Counting Sort Using Arrays
This program shows the classic Counting Sort algorithm for integers. It counts how many times each number occurs and uses that information to reconstruct the sorted array.
open System
let countingSort (arr:int[]) =
let maxVal = Array.max arr
let count = Array.zeroCreate (maxVal + 1)
for i in arr do
count.[i] <- count.[i] + 1
let mutable index = 0
for i in 0 .. maxVal do
for _ in 1 .. count.[i] do
arr.[index] <- i
index <- index + 1
[<EntryPoint>]
let main argv =
let numbers = [|4; 2; 2; 8; 3; 3; 1|]
countingSort numbers
numbers |> Array.iter (printf "%d ")
0In this program, the count array keeps track of the number of occurrences of each value. Then, the program rebuilds the sorted array based on these counts. This approach is very efficient for small integer ranges and helps beginners understand how counting can replace comparisons.
Program 2: Counting Sort with Step-by-Step Printing
This program prints the counting array and the sorted array during each step, making it easier for beginners to understand the process.
open System
let countingSortStep (arr:int[]) =
let maxVal = Array.max arr
let count = Array.zeroCreate (maxVal + 1)
for i in arr do
count.[i] <- count.[i] + 1
printfn "Count array: %A" count
let mutable index = 0
for i in 0 .. maxVal do
for _ in 1 .. count.[i] do
arr.[index] <- i
index <- index + 1
printfn "Array after placing %d: %A" i arr
[<EntryPoint>]
let main argv =
let numbers = [|4; 2; 2; 8; 3; 3; 1|]
countingSortStep numbers
printfn "Final sorted array: %A" numbers
0Step-by-step printing allows beginners to see exactly how the algorithm counts occurrences and then uses them to sort the array. This makes the logic more concrete and easier to follow.
Program 3: Counting Sort for Negative Numbers
Counting Sort can be adapted for negative numbers by shifting the range. This program handles arrays with negative integers efficiently.
open System
let countingSortNegative (arr:int[]) =
let minVal = Array.min arr
let maxVal = Array.max arr
let range = maxVal - minVal + 1
let count = Array.zeroCreate range
for i in arr do
count.[i - minVal] <- count.[i - minVal] + 1
let mutable index = 0
for i in 0 .. range - 1 do
for _ in 1 .. count.[i] do
arr.[index] <- i + minVal
index <- index + 1
[<EntryPoint>]
let main argv =
let numbers = [| -5; -1; -3; -2; -4; -1 |]
countingSortNegative numbers
numbers |> Array.iter (printf "%d ")
0By shifting the numbers so that the smallest value maps to zero, we can still use the counting array effectively. This version helps beginners understand how to adapt Counting Sort for different input ranges.
Program 4: Counting Sort Using Lists
This version uses F# lists and functional programming style. It demonstrates how Counting Sort can be implemented without modifying arrays directly.
open System
let countingSortList (lst:int list) =
let maxVal = List.max lst
let count = Array.zeroCreate (maxVal + 1)
lst |> List.iter (fun x -> count.[x] <- count.[x] + 1)
let rec buildSorted i acc =
if i > maxVal then acc
else
let acc' = List.replicate count.[i] i @ acc
buildSorted (i + 1) acc'
buildSorted 0 [] |> List.rev
[<EntryPoint>]
let main argv =
let numbers = [4; 2; 2; 8; 3; 3; 1]
let sorted = countingSortList numbers
printfn "Sorted list: %A" sorted
0This approach emphasizes immutability and functional thinking. Beginners can see how counting values and building the sorted list works without modifying the original input.
Program 5: Counting Sort with Custom Range
Sometimes the range of numbers is known in advance. This program lets the user define a custom maximum value, which can save memory for large arrays with small ranges.
open System
let countingSortCustom (arr:int[]) maxValue =
let count = Array.zeroCreate (maxValue + 1)
for i in arr do
count.[i] <- count.[i] + 1
let mutable index = 0
for i in 0 .. maxValue do
for _ in 1 .. count.[i] do
arr.[index] <- i
index <- index + 1
[<EntryPoint>]
let main argv =
let numbers = [|4; 2; 2; 3; 1|]
countingSortCustom numbers 4
numbers |> Array.iter (printf "%d ")
0This version is efficient for beginners to understand how memory usage can be optimized by using a known maximum value. It also reinforces the basic principle of Counting Sort.
Program 6: Counting Sort for Both Negative and Positive Numbers
This program demonstrates how to sort an array containing a mix of negative and positive numbers using Counting Sort. By shifting the entire range so that the smallest number maps to zero, we can count all numbers correctly and then shift them back after sorting. This makes it simple and efficient for beginners to understand.
open System
let countingSortMixed (arr:int[]) =
// Find the minimum and maximum values
let minVal = Array.min arr
let maxVal = Array.max arr
let range = maxVal - minVal + 1
// Initialize counting array
let count = Array.zeroCreate range
// Count each number using offset
for i in arr do
count.[i - minVal] <- count.[i - minVal] + 1
// Rebuild the sorted array
let mutable index = 0
for i in 0 .. range - 1 do
for _ in 1 .. count.[i] do
arr.[index] <- i + minVal
index <- index + 1
[<EntryPoint>]
let main argv =
let numbers = [| -5; 3; -1; 7; -3; 2; 0 |]
countingSortMixed numbers
printfn "Sorted array: %A" numbers
0The program first finds the smallest and largest numbers to determine the range. Then it shifts all numbers by subtracting the minimum, allowing the counting array to work with negative numbers as if they were non-negative. After counting and reconstructing the array, the shift is reversed, giving a fully sorted array that includes both negative and positive numbers. This method is simple, memory-efficient for small ranges, and helps beginners see how Counting Sort can be adapted to real-world data.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Counting Sort in simple terms.
Q1. What kind of data is Counting Sort best for?
Counting Sort works best for integers or small-range numeric data because it relies on counting occurrences.
Q2. Is Counting Sort faster than comparison-based sorts?
Yes, for small ranges, Counting Sort can be faster than algorithms like Bubble Sort or Quick Sort because it avoids repeated comparisons.
Q3. Can Counting Sort handle negative numbers?
Yes, by shifting the range so that the smallest number maps to zero, Counting Sort can sort negative numbers as well.
Q4. Does Counting Sort use extra memory?
Yes, it requires a counting array proportional to the range of input values.
Q5. Should beginners learn Counting Sort?
Yes, it teaches important concepts about frequency counting, range mapping, and efficient sorting without comparisons.
Conclusion
Counting Sort is a practical and efficient sorting algorithm for integer data with small ranges. Through multiple F# programs, we explored basic Counting Sort, step-by-step visualization, negative number handling, functional list-based implementation, and custom range optimization.
By practicing these examples, beginners can understand how Counting Sort works, how it differs from comparison-based sorts, and how to adapt it for various data types. It is a great way to build strong foundational skills in algorithmic thinking and F# programming.
