Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (a kind of hashing). Then do some arithmetic operations to calculate the position of each object in the output sequence.
lets assume we have an array where the biggest number in this array is less than or equal to n:
# in this example n is 9.
a[] = {1,2,2,2,2,3,3,5,7,2,8,4,6,7,4,9};
we start by counting the occurences of each number and store them in a secondary array:
for i in a:
b[i] += 1
then we store the last position of the number i in the sorted array a in a different array called c or we can also overwrite b because we don’t need it anymore:
for i in range(1,n):
b[i] +=b[i-1]
we create an array called d with the size equal to a to output the sorted array. to do this we read every cells from a then read the corresponding cell in c and insert the value from the cell in a into the position stored in c and then decrement the c[a[i]] by 1 until the output array is full.
def countSort(arr):
# The output character array that will have sorted arr
output = [0 for i in range(len(arr))]
# Create a count array to store count of individual
# characters and initialize count array as 0
count = [0 for i in range(256)]
# For storing the resulting answer since the
# string is immutable
ans = ["" for _ in arr]
# Store count of each character
for i in arr:
count[ord(i)] += 1
# Change count[i] so that count[i] now contains actual
# position of this character in output array
for i in range(256):
count[i] += count[i-1]
# Build the output character array
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
# Copy the output array to arr, so that arr now
# contains sorted characters
for i in range(len(arr)):
ans[i] = output[i]
return ans
# Driver code
if __name__ == '__main__':
arr = "CodeVerse"
ans = countSort(arr)
print("Sorted character array is % s" % ("".join(ans)))
is this algorithm stable? the answer is no because it reverses the order in the existing array, but we can make it stable by traversing the initial array backwards from n-1 to 0.
since we used 4 separate for loops the time complexity as the name suggest is linear and is equal to
Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys.
def countingSort(arr, exp1):
n = len(arr)
# The output array elements that will have sorted arr
output = [0] * (n)
# initialize count array as 0
count = [0] * (10)
# Store count of occurrences in count[]
for i in range(0, n):
index = arr[i] // exp1
count[index % 10] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output array
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array
i = n - 1
while i >= 0:
index = arr[i] // exp1
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copying the output array to arr[],
# so that arr now contains sorted numbers
i = 0
for i in range(0, len(arr)):
arr[i] = output[i]
# Method to do Radix Sort
def radixSort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1 / exp >= 1:
countingSort(arr, exp)
exp *= 10
# Driver code
if __name__ == '__main__':
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)
for i in arr:
print(i,end=" ")
The time complexity is O(nw) where n is the number of numbers and w is the maximum number of digits.
The space complexity is O(n + w) due to the buckets.
we can also generalize radix sort based on multiple data e.g. student name, graduation year, id number,… which is called bucket sort.