Hi I got this code that uses counting sort and radix sort to sort a list of numb
ID: 3920550 • Letter: H
Question
Hi I got this code that uses counting sort and radix sort to sort a list of numbers.Can u please help change this to sort alphabets instead like 'ab' first then 'ba' then 'bb'.Pleaseee help already posted twice.I know we can use ord and char?
def counting_sort(arr, max_value, get_index):
counts = [0] * max_value
# Counting - O(n)
for a in arr:
counts[get_index(a)] += 1
# Accumulating - O(k)
for i, c in enumerate(counts):
if i == 0:
continue
else:
counts[i] += counts[i-1]
# Calculating start index - O(k)
for i, c in enumerate(counts[:-1]):
if i == 0:
counts[i] = 0
counts[i+1] = c
ret = [None] * len(arr)
# Sorting - O(n)
for a in arr:
index = counts[get_index(a)]
ret[index] = a
counts[get_index(a)] += 1
return ret
def get_digit(n, d):
for i in range(d-1):
n //= 10
return n % 10
def get_num_difit(n):
i = 0
while n > 0:
n //= 10
i += 1
return i
def radix_sort(arr, max_value=26):
num_digits = get_num_difit(max_value)
# O(k(n+k))
for d in range(num_digits):
# Counting sort takes O(n+k)
arr = counting_sort(arr, max_value, lambda a: get_digit(a, d+1))
return arr
Explanation / Answer
Yes you can sort words (group of letters like aa,ab,bb) using radix sort. Radix sort is used to sort digit by digit (in case of numbers) and in case of words it is done letter by letter i.e, based on last letter of each word, we sort the list of words and then using second last letter and so on. So we are going from least significant letter till most significant letter
For example consider list of words abcd,bchi,aacd,bbaa,cccc,caaa
After sorting based on least significant letter i.e last letter in the word we get the order as
bbaa,caaa,cccc,abcd,aacd,bchi
After sorting using second last letter, order is
bbaa,caaa,cccc,abcd,aacd,bchi
After sorting using third last letter, order is
caaa,aacd,bbaa,abcd,cccc,bchi
After sorting using fourth from last i.e, first letter of the word, the order is
aacd,abcd,bbaa,bchi,caaa,cccc
If we have stored the words in a 2d array like word[][], we can access the first letter of all words as word[0][0],word[1][0],word[2][0] and so on and similarly all the other letters
To sort by each letter we can use counting sort
In counting sort for alphabets we take an array of size 26 (one for each alphabet) let it be c[26]
first we store the occurances in c in this way : c[a[i]]++ i.e for each letter in array a we maintain count in array c
Then we form the cumulative sum of array c
Next we have b[c[a[i]]] = a[i] where b is the sorted array and decrement the count of corresponding letter in c by 1 after each iteration
Long answer short the only difference between sorting letters and sorting numbers using counting sort is the size of the count array . In case of letters its fixed and equal to 26 and for numbers it depends on max in the list