Sorting is a fundamental skill in programming, and choosing the right algorithm can make your programs much more efficient. One algorithm that is simple yet powerful is Counting Sort. Unlike comparison-based sorting algorithms such as Quick Sort or Merge Sort, Counting Sort works by counting the number of occurrences of each element. This makes it extremely fast when dealing with integers in a known, limited range.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is widely used in scenarios where performance is critical and the dataset is not too large in terms of its range of values. It is particularly useful in applications like sorting grades, ages, or other categorical numerical data. For beginners, it’s a great way to understand how we can sort data efficiently without doing repeated comparisons, and it shows how clever use of extra memory can simplify the sorting process.
Program 1: Basic Counting Sort for Integers
This program demonstrates a straightforward implementation of Counting Sort for a simple array of integers. It counts the frequency of each number and then rebuilds the sorted array.
import Foundation
func countingSort(_ array: [Int]) -> [Int] {
guard let maxValue = array.max() else { return array }
var count = Array(repeating: 0, count: maxValue + 1)
var sorted = [Int]()
for number in array {
count[number] += 1
}
for i in 0...maxValue {
while count[i] > 0 {
sorted.append(i)
count[i] -= 1
}
}
return sorted
}
let data1 = [4, 2, 2, 8, 3, 3, 1]
let sortedData1 = countingSort(data1)
print("Sorted array:", sortedData1)This program works by creating a count array that tracks how many times each number appears. Then, by iterating through this count array, we build the sorted output. Beginners can see how Counting Sort avoids repeated comparisons and produces a fast, stable sort.
Program 2: Counting Sort with Negative Integers
Counting Sort traditionally works with non-negative integers. To handle negative numbers, we can shift all values by the minimum number in the array so they become non-negative.
import Foundation
func countingSortWithNegatives(_ array: [Int]) -> [Int] {
guard let minValue = array.min(), let maxValue = array.max() else { return array }
let range = maxValue - minValue + 1
var count = Array(repeating: 0, count: range)
var sorted = [Int]()
for number in array {
count[number - minValue] += 1
}
for i in 0..<range {
while count[i] > 0 {
sorted.append(i + minValue)
count[i] -= 1
}
}
return sorted
}
let data2 = [4, -2, -2, 8, 3, -1, 1]
let sortedData2 = countingSortWithNegatives(data2)
print("Sorted array with negatives:", sortedData2)By shifting the array so that the smallest number becomes zero, we can use the same counting logic. This approach helps beginners understand how Counting Sort can be extended to handle negative integers without changing the core algorithm.
Program 3: Counting Sort for Large Range of Integers
When the integer range is large, Counting Sort can be memory-intensive. This program demonstrates sorting with a large dataset by calculating the required count array size dynamically.
import Foundation
func countingSortLargeRange(_ array: [Int]) -> [Int] {
guard let minValue = array.min(), let maxValue = array.max() else { return array }
var count = Array(repeating: 0, count: maxValue - minValue + 1)
var sorted = [Int]()
for num in array {
count[num - minValue] += 1
}
for i in 0..<count.count {
while count[i] > 0 {
sorted.append(i + minValue)
count[i] -= 1
}
}
return sorted
}
let data4 = [100, 3, 50, 200, 150]
let sortedData4 = countingSortLargeRange(data4)
print("Sorted array with large range:", sortedData4)This approach shows beginners how to handle datasets with a large spread of numbers efficiently, while still using the same counting logic.
Program 4: Generic Counting Sort for Limited Range
While Counting Sort is traditionally used for integers, we can generalize it with Swift generics to work with any type that can be mapped to a non-negative integer index, including scores, categorical numbers, or other numeric representations.
import Foundation
func universalCountingSort<T>(
_ array: [T],
keyFunction: ((T) -> Double)? = nil,
scale: Int = 1000
) -> [T] {
guard !array.isEmpty else { return array }
// Compute keys for counting sort
let keys: [Int] = array.map { item in
if let keyFunc = keyFunction {
// If a key function is provided, use it
return Int((keyFunc(item) * Double(scale)).rounded())
} else if let num = item as? Double {
// Handle Double (can include negatives)
let minValue = array.compactMap { $0 as? Double }.min() ?? 0
return Int(((num - minValue) * Double(scale)).rounded())
} else if let num = item as? Int {
// Handle Int (can include negatives)
let minValue = array.compactMap { $0 as? Int }.min() ?? 0
return num - minValue
} else {
fatalError("Type not supported without key function")
}
}
// Counting sort
let maxKey = keys.max()!
var count = Array(repeating: [T](), count: maxKey + 1)
for (i, key) in keys.enumerated() {
count[key].append(array[i])
}
return count.flatMap { $0 }
}
// 1. Positive integers
let intData = [15, 42, 37, 8, 23, 4]
print("Sorted integers:", universalCountingSort(intData))
// 2. Negative and positive integers
let negIntData = [-15, 42, -37, 8, -23, 4]
print("Sorted negative and positive integers:", universalCountingSort(negIntData))
// 3. Positive doubles
let doubleData: [Double] = [0.25, 0.36, 0.58, 0.41, 0.29, 0.22]
print("Sorted doubles:", universalCountingSort(doubleData))
// 4. Doubles including negatives
let doubleDataNeg: [Double] = [-0.4, 0.25, -0.1, 0.75, 0.0, -0.9]
print("Sorted doubles including negatives:", universalCountingSort(doubleDataNeg))
// 5. Tuples with integer key
let tupleData: [(String, Int)] = [("Alice", 3), ("Bob", 1), ("Charlie", 2)]
let sortedTuples = universalCountingSort(tupleData, keyFunction: { Double($0.1) })
print("Sorted tuples by score:", sortedTuples)This version adds flexibility, enabling Counting Sort to handle tuples or custom objects by using a key for indexing. Beginners can easily see how the algorithm adapts to different kinds of data while keeping the core sorting logic unchanged, making it both versatile and easy to understand.
Frequently Asked Questions (FAQ)
This section answers common questions beginners ask about Counting Sort in Swift.
Q1: Can Counting Sort handle negative numbers?
Yes, by shifting the numbers so the minimum becomes zero, negative values can be handled efficiently.
Q2: Is Counting Sort stable?
Yes, Counting Sort is stable, meaning elements with equal keys retain their original relative order.
Q3: What is the time complexity of Counting Sort?
It runs in O(n + k) time, where n is the number of elements and k is the range of input numbers.
Q4: Can Counting Sort work with non-integer data?
Yes, if you can map your data to integer keys, Counting Sort can handle it, as shown in the generic example.
Q5: When should I avoid Counting Sort?
It is not efficient for datasets with a very large range of numbers, as the count array could use too much memory.
Conclusion
Counting Sort is a simple, efficient, and stable sorting algorithm for integers and data that can be mapped to integer keys. By understanding how to count occurrences and rebuild the sorted array, beginners can learn an important strategy for optimizing sorting performance. Variations like handling negative numbers, returning new arrays, and working with generic data make Counting Sort a versatile tool in Swift programming. Practicing these examples helps build confidence in applying sorting techniques to real-world datasets.
