FAQ: Radix Sort: Python - Review (and Bug Fix!)


#1

This community-built FAQ covers the “Review (and Bug Fix!)” exercise from the lesson “Radix Sort: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Sorting Algorithms

FAQs on the exercise Review (and Bug Fix!)

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!


#2

Hi, everyone. I have a question on the radix sort algorithm. I don’t understand how the values become sorted within each bucket in the digits variable during the last iteration. For example if it encounters 559 then 529 then 524 in this order in the unsorted list but when i appends it in the 5-bucket of the digits variable…it returns it sorted as [524,529,559]. How does this happen with the append method used? Also I noticed this was not the case for the first two iterations of the algorithm (the digits array was returned unsorted within each bucket).


#3

I’m only now working my way through the module and will attempt to guide you toward an explanation, whence it gets disseminated in my own mind.

Having only just completed Lesson 3, Bucketing Numbers, I wanted to see what we have at this point for data structures. To that end I added a random sequence generator for testing.

from random import randrange

def rand_list(n, r):    # n => sample size; r => range for each value
    return [randrange(r) for _ in range(n)]

Random output…

>>> radix_sort(rand_list(20, 100))
[[70, 70, 50], [41], [32, 62, 32], [73], [54, 34], [35], [56, 26, 86, 26], [47], [88], [59, 19, 69]]
>>> 

We can visualize the least significant digit ordered within the structure.

Will press on and hope to catch up, presently. 10-4

After lesson 4…

>>> radix_sort(rand_list(20, 100))
[90, 30, 90, 90, 11, 11, 52, 53, 3, 93, 15, 85, 96, 47, 17, 38, 58, 58, 8, 9]
>>> 

After lesson 5…

Due to the nature of my random list, not all numbers will have the same number of digits. I wrapped the two lines affected by this in a try-except handler…


      try:
        digit = number_as_a_string[index]
        digit = int(digit)
      except IndexError:
        continue

That cured the frequent exceptions I was running into during testing.

>>> radix_sort(rand_list(10, 100))
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-2
-2
Traceback (most recent call last):
  File "<pyshell#20>", line 1, in <module>
    radix_sort(rand_list(10, 100))
  File "D:/cc/Learn/Python 3/radix_sort.py", line 23, in radix_sort
    digit = number_as_a_string[index]
IndexError: string index out of range
>>> 
================ RESTART: D:/cc/Learn/Python 3/radix_sort.py ================
>>> radix_sort(rand_list(10, 100))
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-2
-2
-2
-2
-2
-2
-2
-2
-2
-2
[11, 21, 32, 38, 39, 40, 66, 67, 70, 74]
>>> 

I had inserted a print statement in my test code so I could see what was happening the loop.

Lesson 6…

Oops! Looks like I got ahead of the game. Will have to see how the author handles this. 10-4


#4

Use this to visualize the whole process…

      digits[digit].append(number)
      print ((number, digit), digits)

Extra Study

The narrative alluded to mathematical approaches to this sort method on the proviso we garnered the intuition from the naive string approach. I’m guessing we have so can venture down the rabbit hole.

Let’s start with max_exponent. The name itself is synonymous with logarithm, base 10. What is the log base 10 of 10 to the 5th power? 5.

The author has deliberately made the max_exponent one more than this because it is passed to the range() function later, which we know excludes the upper bound but still gives us six iterations, one for each digit.

Now knowing that we can arrive at this number without calling the len() function on a superimposed string object means we must pursue it…

If log base 10 of 10 to the 5 is 5, what is the ceiling of that log?

>>> from math import log10, ceil
>>> ceil(log10(100000))
5
>>> ceil(log10(10 ** 5))
5
>>> x = 10e5
>>> ceil(log10(x))
6
>>> 

Ignore the last one. I couldn’t possibly explain this anomaly. It has something to do with limits and/or floating point arithmetic, one suspects. It might be we can see the behavior induced on our other values just with a tiny tickle…

>>> ceil(log10(100001))
6
>>> ceil(log10(10 ** 5 + 1))
6
>>> 

Given that we trust our function to produce the correct number of digits,

max_exponent = ceil(log10(maximum_value + 1))

Food for thought…

>>> ceil(log10(999 + 1))
3
>>> ceil(log10(799 + 1))
3
>>> ceil(log10(1e2 + 1))
3
>>> 

This is a lot of crazy math to warp one’s head around, but not that difficult to visualize, if one is so inclined. Go over and over it as much as needed to get to the crunch. When it hits, you’ll know it.

Plus one pushes the boundaries into the next degree. It’s more than floating point can endure without reacting accordingly. All in all it gives us a stable platform from which to work our math.