# radixSort.py

import math, time
from arrUtils import *


def radixSort(elems):
  numDigits = int(math.log10(max(elems))) + 1
  for pos in range(numDigits+1):
    buckSort(elems, pos)


def buckSort(elems, pos):
  # clear digits buckets
  buckets = [[] for _ in range(10)]    

  # Distribute the elements from elems to buckets
  for i in range(len(elems)):
    key = posDigit(elems[i], pos)
    buckets[key].append(elems[i])

  # Now move the elements from the buckets back to elems
  k = 0 # k is an index for elems
  for i in range(10):
    for j in range(len(buckets[i])):
      elems[k] = buckets[i][j]
      k += 1


def posDigit(n, pos):
  ''' Return the digit at the specified pos. 
   The right-most digit's pos = 0. 
  '''
  pow = 1;
  for i in range(pos):
    pow *= 10
  return (n // pow) % 10


if __name__ == "__main__":
  n = int(input("n? "))
  elems = genArr(n)
  start = time.time()
  radixSort(elems)
  printPartArr(elems)
  print(f"Time: {(time.time()-start):.4f} secs")