Advertisement
bwukki

Radix sort in py

Oct 11th, 2018
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.95 KB | None | 0 0
  1. #bin class
  2.  
  3.  
  4. class Bin:
  5.  
  6.     def __init__(self):
  7.         """Takes in no args, initializes to an empty list"""
  8.         self.content = []
  9.  
  10.     def push(self,a_input):
  11.         """Adds an item to the front of the que"""
  12.         self.content.append(a_input)
  13.  
  14.     def pop(self):
  15.         """Returns the item at the front of the que, then deletes it"""
  16.         self.check_empty()
  17.         result = self.content[0]
  18.         del self.content[0]
  19.         return result
  20.  
  21.     def peek(self):
  22.         """Returns the item at the front of the que"""
  23.         self.check_empty()
  24.         return self.content[0]
  25.  
  26.     def check_empty(self):
  27.         """Raises an error if the list if empty"""
  28.         if len(self.content) == 0:
  29.             raise Exception("Bin is empty")
  30.  
  31.     def check_size(self):
  32.         return len(self.content)
  33.  
  34.  
  35.  
  36. #bin unit tests
  37.  
  38. import unittest
  39. import Bin
  40.  
  41.  
  42. class BinTest(unittest.TestCase):
  43.  
  44.     def testBin(self):
  45.         x = Bin.Bin()
  46.         x.push(1)
  47.         self.assertEqual(x.peek(),1)
  48.         x.push(2)
  49.         self.assertEqual(x.pop(),1)
  50.         self.assertEqual(x.peek(),2)
  51.         self.assertEqual(x.pop(), 2)
  52.         self.assertRaises(Exception, x.check_empty)
  53.         self.assertRaises(Exception, x.peek)
  54.         self.assertRaises(Exception, x.pop)
  55.  
  56.  
  57. if __name__ == '__main__':
  58.     unittest.main()
  59.  
  60.  
  61. #radix class
  62.  
  63. import Bin
  64.  
  65. class Radix:
  66.  
  67.     def __init__(self):
  68.         self.one = Bin.Bin()
  69.         self.two = Bin.Bin()
  70.         self.three = Bin.Bin()
  71.         self.four = Bin.Bin()
  72.         self.five = Bin.Bin()
  73.         self.six = Bin.Bin()
  74.         self.seven = Bin.Bin()
  75.         self.eight = Bin.Bin()
  76.         self.nine = Bin.Bin()
  77.         self.zero = Bin.Bin()
  78.         self.main = Bin.Bin()
  79.  
  80.     @staticmethod
  81.     def check_if_list(args):
  82.          if type(args) != list:
  83.             raise TypeError("Must take in a list")
  84.  
  85.     @staticmethod
  86.     def split_string(args):
  87.         """Turns all list items into strings as preparation for manipulation"""
  88.         Radix.check_if_list(args)
  89.         for i in range(len(args)):
  90.             args[i] = str(args[i])
  91.         return args
  92.  
  93.     @staticmethod
  94.     def equalize(args):
  95.         """Formats all list items to have the same # of digits, ex 200, 2, 20 become 200, 002, 020 - probably
  96.         unneccesary and can be removed and refactored if performance is an issue, returns max length of items in arg"""
  97.         max_len = Radix.get_max_len(args)
  98.         index = 0
  99.         for i in args:
  100.             while len(str(i)) < max_len:
  101.                 i = "0" + i
  102.             args[index] = i
  103.             index += 1
  104.         return args
  105.  
  106.     def print(self):
  107.         while self.main.check_size() > 0:
  108.             print(self.main.pop())
  109.  
  110.     @staticmethod
  111.     def get_max_len(args):
  112.         max_len = 0
  113.         for i in args:
  114.             if len(str(i)) > max_len:
  115.                 max_len = len(str(i))
  116.         return max_len
  117.  
  118.     def sort(self, args):
  119.         args = Radix.split_string(args) #converts the list to strings
  120.         args = Radix.equalize(args) #makes all the values in the list the same size (appends zeros to the front)
  121.         size_of = len(args)
  122.         max_len = Radix.get_max_len(args)-1
  123.         for i in args:
  124.             self.main.push(i) #starts by throwing all of the values into the main bin
  125.         for i in range(max_len+1): #for every digit, split the digits into their respective buckets and then throw them back into main
  126.             self.split_digits(i,max_len)
  127.  
  128.  
  129.     def place_into_bucket(self,num,max_len):
  130.         if self.main.peek()[max_len-num] == '0':
  131.             self.zero.push(self.main.pop())
  132.         elif self.main.peek()[max_len - num] == '1':
  133.              self.one.push(self.main.pop())
  134.         elif self.main.peek()[max_len - num] == '2':
  135.             self.two.push(self.main.pop())
  136.         elif self.main.peek()[max_len - num] == '3':
  137.             self.three.push(self.main.pop())
  138.         elif self.main.peek()[max_len - num] == '4':
  139.             self.four.push(self.main.pop())
  140.         elif self.main.peek()[max_len - num] == '5':
  141.             self.five.push(self.main.pop())
  142.         elif self.main.peek()[max_len - num] == '6':
  143.             self.six.push(self.main.pop())
  144.         elif self.main.peek()[max_len - num] == '7':
  145.             self.seven.push(self.main.pop())
  146.         elif self.main.peek()[max_len - num] == '8':
  147.             self.eight.push(self.main.pop())
  148.         elif self.main.peek()[max_len - num] == '9':
  149.             self.nine.push(self.main.pop())
  150.         """Determines which bucket the number should go in, then puts it in there while popping it off main"""
  151.  
  152.     def empty_buckets(self):
  153.         """Removes all values from buckets, puts them all into main bucket in order"""
  154.         while self.zero.check_size() > 0:
  155.             self.main.push(self.zero.pop())
  156.         while self.one.check_size() > 0:
  157.             self.main.push(self.one.pop())
  158.         while self.two.check_size() > 0:
  159.             self.main.push(self.two.pop())
  160.         while self.three.check_size() > 0:
  161.             self.main.push(self.three.pop())
  162.         while self.four.check_size() > 0:
  163.             self.main.push(self.four.pop())
  164.         while self.five.check_size() > 0:
  165.             self.main.push(self.five.pop())
  166.         while self.six.check_size() > 0:
  167.             self.main.push(self.six.pop())
  168.         while self.seven.check_size() > 0:
  169.             self.main.push(self.seven.pop())
  170.         while self.eight.check_size() > 0:
  171.             self.main.push(self.eight.pop())
  172.         while self.nine.check_size() > 0:
  173.             self.main.push(self.nine.pop())
  174.  
  175.     def split_digits(self,num,max_len):
  176.         while self.main.check_size() > 0:
  177.             self.place_into_bucket(num,max_len)
  178.         self.empty_buckets()
  179.  
  180.  
  181. #main
  182.  
  183. import Radix
  184.  
  185. x = Radix.Radix()
  186.  
  187. y = [123,456,789,101112,542,1234993,324903249239,352,1234234,3212,1234234523,342564,656,7657,856765,435324,12312,5435,67,654546,75454678,8657657]
  188. x.sort(y)
  189. x.print()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement