prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Bug report for radix sort
  **Description**
  
  if the test case for [`radix_sort.py`](https://github.com/TheAlgorithms/Python/blob/master/sorts/radix_sort.py) is `[104, 203, 308, 401]`, the result would be `[401, 203, 104, 308]`
  
  It's wrong!
  
  The reason is that if the `tmp` is always `0` in one loop, it will exit the loop. In other words, If the same digit of all numbers is 0, then the result may be wrong. The similar example like:
  *Input*: `[2018, 33017, 24016]`
  *Output*: `[24016, 33017, 2018]`
  Wrong again!!
  
  **Suggestion**
  
  Do not use `maxLength` as a loop variable because the value of `maxLength` is related to `tmp`.
  
  I think that by finding the maximum value of the array and assigning it to `max_digit`, using another variable `digit` with an initial value of 1 as the loop variable, each loop `digit`  is multiplied by 10, and exit the loops when the `digit` greater than `max_digit`, which can guarantee the correct number of loops.
  
  And the complexity will be O(nk + n) . n is the size of input list and k is the digit length of the number.
  
  </issue>
  <code>
  [start of sorts/radix_sort.py]
  1 def radixsort(lst):
  2   RADIX = 10
  3   maxLength = False
  4   tmp , placement = -1, 1
  5 
  6   while not maxLength:
  7     maxLength = True
  8     # declare and initialize buckets
  9     buckets = [list() for _ in range( RADIX )]
  10 
  11     # split lst between lists
  12     for i in lst:
  13       tmp = int((i / placement) % RADIX)
  14       buckets[tmp].append(i)
  15 
  16       if maxLength and tmp > 0:
  17         maxLength = False
  18 
  19     # empty lists into lst array
  20     a = 0
  21     for b in range( RADIX ):
  22       buck = buckets[b]
  23       for i in buck:
  24         lst[a] = i
  25         a += 1
  26 
  27     # move to next
  28     placement *= RADIX
  29
  [end of sorts/radix_sort.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/sorts/radix_sort.py b/sorts/radix_sort.py
  --- a/sorts/radix_sort.py
  +++ b/sorts/radix_sort.py
  @@ -1,28 +1,26 @@
   def radixsort(lst):
  -  RADIX = 10
  -  maxLength = False
  -  tmp , placement = -1, 1
  +    RADIX = 10
  +    placement = 1
   
  -  while not maxLength:
  -    maxLength = True
  -    # declare and initialize buckets
  -    buckets = [list() for _ in range( RADIX )]
  +    # get the maximum number
  +    max_digit = max(lst)
   
  -    # split lst between lists
  -    for i in lst:
  -      tmp = int((i / placement) % RADIX)
  -      buckets[tmp].append(i)
  +    while placement < max_digit:
  +      # declare and initialize buckets
  +      buckets = [list() for _ in range( RADIX )]
   
  -      if maxLength and tmp > 0:
  -        maxLength = False
  +      # split lst between lists
  +      for i in lst:
  +        tmp = int((i / placement) % RADIX)
  +        buckets[tmp].append(i)
   
  -    # empty lists into lst array
  -    a = 0
  -    for b in range( RADIX ):
  -      buck = buckets[b]
  -      for i in buck:
  -        lst[a] = i
  -        a += 1
  +      # empty lists into lst array
  +      a = 0
  +      for b in range( RADIX ):
  +        buck = buckets[b]
  +        for i in buck:
  +          lst[a] = i
  +          a += 1
   
  -    # move to next
  -    placement *= RADIX
  +      # move to next
  +      placement *= RADIX
  
verification_info: {"golden_diff": "diff --git a/sorts/radix_sort.py b/sorts/radix_sort.py\n--- a/sorts/radix_sort.py\n+++ b/sorts/radix_sort.py\n@@ -1,28 +1,26 @@\n def radixsort(lst):\n-  RADIX = 10\n-  maxLength = False\n-  tmp , placement = -1, 1\n+    RADIX = 10\n+    placement = 1\n \n-  while not maxLength:\n-    maxLength = True\n-    # declare and initialize buckets\n-    buckets = [list() for _ in range( RADIX )]\n+    # get the maximum number\n+    max_digit = max(lst)\n \n-    # split lst between lists\n-    for i in lst:\n-      tmp = int((i / placement) % RADIX)\n-      buckets[tmp].append(i)\n+    while placement < max_digit:\n+      # declare and initialize buckets\n+      buckets = [list() for _ in range( RADIX )]\n \n-      if maxLength and tmp > 0:\n-        maxLength = False\n+      # split lst between lists\n+      for i in lst:\n+        tmp = int((i / placement) % RADIX)\n+        buckets[tmp].append(i)\n \n-    # empty lists into lst array\n-    a = 0\n-    for b in range( RADIX ):\n-      buck = buckets[b]\n-      for i in buck:\n-        lst[a] = i\n-        a += 1\n+      # empty lists into lst array\n+      a = 0\n+      for b in range( RADIX ):\n+        buck = buckets[b]\n+        for i in buck:\n+          lst[a] = i\n+          a += 1\n \n-    # move to next\n-    placement *= RADIX\n+      # move to next\n+      placement *= RADIX\n", "issue": "Bug report for radix sort\n**Description**\r\n\r\nif the test case for [`radix_sort.py`](https://github.com/TheAlgorithms/Python/blob/master/sorts/radix_sort.py) is `[104, 203, 308, 401]`, the result would be `[401, 203, 104, 308]`\r\n\r\nIt's wrong!\r\n\r\nThe reason is that if the `tmp` is always `0` in one loop, it will exit the loop. In other words, If the same digit of all numbers is 0, then the result may be wrong. The similar example like:\r\n*Input*: `[2018, 33017, 24016]`\r\n*Output*: `[24016, 33017, 2018]`\r\nWrong again!!\r\n\r\n**Suggestion**\r\n\r\nDo not use `maxLength` as a loop variable because the value of `maxLength` is related to `tmp`.\r\n\r\nI think that by finding the maximum value of the array and assigning it to `max_digit`, using another variable `digit` with an initial value of 1 as the loop variable, each loop `digit`  is multiplied by 10, and exit the loops when the `digit` greater than `max_digit`, which can guarantee the correct number of loops.\r\n\r\nAnd the complexity will be O(nk + n) . n is the size of input list and k is the digit length of the number.\n", "before_files": [{"content": "def radixsort(lst):\n  RADIX = 10\n  maxLength = False\n  tmp , placement = -1, 1\n\n  while not maxLength:\n    maxLength = True\n    # declare and initialize buckets\n    buckets = [list() for _ in range( RADIX )]\n\n    # split lst between lists\n    for i in lst:\n      tmp = int((i / placement) % RADIX)\n      buckets[tmp].append(i)\n\n      if maxLength and tmp > 0:\n        maxLength = False\n\n    # empty lists into lst array\n    a = 0\n    for b in range( RADIX ):\n      buck = buckets[b]\n      for i in buck:\n        lst[a] = i\n        a += 1\n\n    # move to next\n    placement *= RADIX\n", "path": "sorts/radix_sort.py"}]}