m2skills

Bucket sort python

Sep 28th, 2017
25
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.33 KB | None | 0 0
  1. # program to implement Bucket sort algorithm in python
  2. from itertools import chain
  3.  
  4. # method that sorts the list
  5. def bucket_sort(myList):
  6.    
  7.     # finding the max element
  8.     max_element = max(myList)
  9.    
  10.     # couting the number of digits in the max element
  11.     digits = 0
  12.     while max_element != 0:
  13.         max_element = int(max_element / 10)
  14.         digits += 1
  15.    
  16.     # raising divisor by number of digits
  17.     divisor = 10
  18.     d = divisor
  19.     # loop while divisor does not become 0
  20.     while divisor < d**(digits+1):
  21.         # initializing radix as 10 empty lists
  22.         Radix = [[] for _ in range(10)]
  23.         # iterating over the list
  24.         for element in myList:
  25.             # finding the bucket where the element need to be inserted
  26.             rem = element % divisor
  27.             pos = int(rem / (divisor/10))
  28.             # print(element, divisor, rem, pos)
  29.             Radix[pos].append(element)
  30.        
  31.         print("\nAfter dividing by {0} the buckets are : ".format(divisor))
  32.         print(Radix)
  33.         # divide divisor by 10
  34.         divisor = int(divisor * 10)
  35.         myList = list(chain.from_iterable(Radix))
  36.         # print(myList)
  37.        
  38.     return myList
  39.        
  40. print("Program to implement Bucket sort algorithm in python")
  41. myList = list(map(int, input("\nEnter the elements to sorted as spaced integers : ").strip().split()))
  42. print("The list before sorting is : ")
  43. print(myList)
  44. myList = bucket_sort(myList)
  45. print("\nThe sorted list is : ")
  46. print(myList)
Add Comment
Please, Sign In to add comment