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

[wiki-bot]

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 () 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 () below!

Agree with a comment or answer? 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!

[daab4real]

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).

[mtf]

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

[mtf]

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.

[tombrophy]

I’m having a similar problem with the second lesson as I get this message:

Did you comment out your call to radix_sort on the unsorted_list?

This is my current code:

def radix_sort(to_be_sorted):
  maximum_value = max(to_be_sorted)
  max_exponent = len(str(maximum_value))
  being_sorted = to_be_sorted[:]

  for exponent in range(max_exponent):
    position = exponent + 1
    index = -position

    digits = [[] for i in range(10)]

    for number in being_sorted:
      number_as_a_string = str(number)
      digit = number_as_a_string[index]
      digit = int(digit)

      digits[digit].append(number)

    being_sorted = []
    for numeral in digits:
      being_sorted.extend(numeral)

  return being_sorted

unsorted_list = [830, 921, 163, 373, 961, 559, 89, 199, 535, 959, 40, 641, 355, 689, 621, 183, 182, 524, 1]
#print(radix_sort(unsorted_list))

[tag0032724846]

I had the same problem. I looked in the folder to see if the test file was visible so I could see what it is checking for, but it is hidden. I just worked through the rest of the exercise ignoring the error popup, then after finishing it I just hit the Get Solution to move forward.

[array8683189266]

Here is a version of radix_sort that doesn’t use strings, it is a bit simpler as it does away with the index and also the need to check for an index error. The maths takes care of that and returns zero when looking at a number with no digit in the position being calculated.

from math import log10

def radix_sort(to_be_sorted):
    maximum_value = max(to_be_sorted)
    max_exponent = int(log10(maximum_value) + 1)
    being_sorted = to_be_sorted[:]

    # create for loop here:
    for exponent in range(max_exponent):
        position = exponent + 1
        digits = [[] for i in range(10)]

        for number in being_sorted:
            digit = int(number % (10 ** position) // (10 ** (position - 1)))
            digits[digit].append(number)

        being_sorted = []
        for numeral in digits:
            being_sorted.extend(numeral)
    return being_sorted

[creence]

When you first call radix_sort(unsorted_list) in review and bug fix, you don’t have to print it. At the end of the lesson you do. I got a similar error message at the end of my lesson, because I put more than one line in my try block so it wasn’t related to the error message at all.

[css3086820884]

max_exponent = int(log10(maximum_value) + 1)
for maximum_value = 1000 for example, this returns 3, and we need our max_exponent to be 4 there

I think we should use max_exponent = ceil(log10(maximum_value) + 1) as mtf suggested.
But the sort seems to be working nevertheless. Can someone explain, please? How it is it works even though it doesn’t loop through the correct max_exponent?