import numpy as np
def countsort(arr):
"""
Sort an array using count sort, assuming, for simplicity,
that arr contains only nonnegative integers
Parameters
----------
arr: list
"""
if len(arr) > 0:
## Step 1: Find the maximum element of the array
max_elem = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_elem:
max_elem = arr[i]
## Step 2: Create an array of length max_elem+1 and
## store the counts at each element
counts = [0]*(max_elem+1)
for x in arr:
counts[x] += 1
## Step 3: Loop through the counts array and put elements
## at their appropriate place
idx = 0
for x, count in enumerate(counts):
for k in range(count):
arr[idx] = x
idx += 1
Time complexity of countsort is $O(M + N)$ for a maximum digit of $M$ and $N$ numbers. This is OK if $M$ is small, but we're in big trouble otherwise.
Ex) If we have the numbers $1e9, 2, 5, 6e12$, $N = 4$, but $M = 6e12$
np.random.seed(0)
arr = np.random.randint(0, 100, 20).tolist()
print(arr)
countsort(arr)
print(arr)
def get_base10(x, place):
"""
Return the digit at a particular place in a
base 10 number
Parameters
----------
x: int
An integer
place: int
Which place to look at, where 0 is the 1s place,
1 is the 10s place, 2 is the 100s place, etc
"""
digit = 0
s = "{}".format(x)
if place < len(s):
digit = int(s[-(1+place)])
return digit
def radixsort(arr):
"""
Sort an array using radix sort, assuming, for simplicity,
that arr contains only nonnegative integers
Parameters
----------
arr: list
"""
if len(arr) > 0:
## Find out the maximum number of digits needed to
## represent a number in this array. This will be
## the number of rounds in radix sort
digits = 0
for i in range(1, len(arr)):
digits = max(digits, len("{}".format(arr[i])))
for place in range(digits):
staging = [0]*len(arr)
counts = [0]*10
## TODO: Perform a count sort, but only using
## the digits at the place "place." Based on
## the counts, move the elements in arr into the
## staging area list
for x in arr:
counts[get_base10(x, place)] += 1
## Create an array csum, where csum[d] holds
## the index in the staging area where we should place
## the next element with with digit d in this place
# Ex) 70 600 192 472 763 723 684 754 804 314 835 705 396 707 277 559 629 359 9 599
# Ex) 0 1 2 3 4 5 6 7 8 9
# 5 1 2 1 0 3 1 3 1 3
# 0 0 0 0 0 1 2 2 3 5 5 5 6 7 7 7 8 9 9 9
# 0s: 0, 1s: 5, 2s: 6, 3s: 8, 4s: 9, 5s: 9, 6s: 12
csum = [0]*10
for i in range(1, 10):
csum[i] = csum[i-1] + counts[i-1]
## TODO: Loop through arr. For each element x, get the
## digit d at the current place, put that element
## in the staging area according to csum[d], and
## then increment csum[d] so we know where to place
## the next element with digit d
# Copy elements back
for i in range(len(arr)):
arr[i] = staging[i]
print(arr)