RADIX Sort in Python | tutorial and how to implement in code

Learn how the Radix Sort (Bucket Sort) algorithm works step by step, and how to implement it in Python code in this tutorial how-to.

PYTHON SORTING ALGORITHMS

#Python

[arshakyessayan]

Function __get_num_digits could be written better.

return len( str( max( A ) ) )

It works faster and it is easier to understand.

[brotherlui]

Hi Joe, many thanks for this video. One suggestion; I'd put the __get_num_digits() function call into the radix() function and call it just with the list to be sorted as parameter. imho

[AlexandrBorschchev]

I stopped python some months ago. getting back again through your videos.

[Mr_Yod]

I have another suggestion: put the exponent outside the second for, this way if you have a list of 10M numbers with 8 digits, the program will have to calculate the exponent only 8 times instead of 80 milion times.
So:
e = 10 ** digit
for item in A:
num = item // e % 10

From 37~40s to 24s (12s to generate the list [randint(0, 10 ** 8) for _ in range(10 ** 7)])

[rayj]

Been waiting for yah joe! Happy to see you’re back

[charithgowda_]

Even though u take d explanation fast..it's just awesome

[Karim-nqbe]

Thanks I liked the idea of using lists of lists (what you called "buckets") and flatten it after. Even though it's not efficient memory wise.

[casualgamer]

gpt>is bucket sort same as radix sort
ChatGPT
No, Bucket Sort and Radix Sort are not the same sorting algorithms, although they share some similarities and can be used together in certain cases to improve performance.

[glebignites]

Thank you Joe. This was very informative and well-explained.

[shubhanshusharma]

One request pls make more video on data structure anr algorithm for python

[vector]

Radix sort is what turned me on to sorting algos to begin with.

[MrBabaum]

Great explanation! With some extra steps this could work for negative numbers too

[Mr_Yod]

There's no need to iterate every item in the list to find the max value: you can use max on the list itself:
m = max(lis)
So __get_num_digits(lis) just becomes:
num_digits = len(str(max(lis)))

With max([], default=0) the function will return a 0 if the list is empty

[diaz]

for short code you can use return len(str(max(a)))

[prch]

Great video! I have a question: wouldn't the nested loops give you an O(n^2) complexity? (As you can probablly tell, I'm a beginner)

[marcelomelo]

def radix_sort(iterable):
all_values = []
for i in iterable:
for j in range(0, len(str(i))):
digit = int(str(i)[j])
try:

except IndexError:
all_values.append([[] if c != digit else [i] for c in range(10)])
return [numbers for obj in all_values for lists in obj for numbers in sorted(filter(None, lists))][:len(iterable)]

[maitri]

can someone tell what is the prioriy order in the expression num=item//10**(digit)%10

[missyhala]

Isn't calling other functions in a function considered branching?

[AlexandrBorschchev]

Hi joe, is radix sort the fastest way for sorting larger lists?

[mearaftadewos]

Radix sort has a bug.
It doesn't sort properly if the array contains numbers with different digit and the left most digit of the smaller number is grater than of the corresponding digit value of the bigger number.

print(radix([900, 1000, 10, 2000, 4002]))


output: [ 900, 10, 1000, 2000, 4002 ]
You can see the 900 and 10 are misplaced