Advertisement
Skysong80

Timed Bubble, Merge & Tomsort

May 3rd, 2019
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. from timeit import timeit
  2. from random import randint
  3.  
  4. def bubble_sort(myList):
  5. swapped = True
  6. while swapped:
  7. swapped = False
  8. for i in range(len(myList) - 1):
  9. if myList[i] > myList[i+1]:
  10. myList[i], myList[i+1] = myList[i+1], myList[i]
  11. swapped = True
  12. return myList
  13.  
  14. def merge(list_a, list_b):
  15. list_c = []
  16. while len(list_a) > 0 and len(list_b) > 0:
  17. if list_a[0] < list_b[0]:
  18. list_c.append(list_a.pop(0))
  19. else:
  20. list_c.append(list_b.pop(0))
  21. if list_a == []:
  22. list_c += list_b
  23. else:
  24. list_c += list_a
  25. #print("merged list is", list_c)
  26. return list_c
  27.  
  28.  
  29. def merge_sort(unsorted):
  30. if len(unsorted) < 2:
  31. return unsorted
  32. else:
  33. middle = len(unsorted) // 2
  34. front = unsorted[:middle]
  35. back = unsorted[middle:]
  36. #print("splits are", front, back)
  37. front = merge_sort(front)
  38. back = merge_sort(back)
  39. return merge(front, back)
  40.  
  41. #Generate a large (1000 items) random list
  42. list_to_sort = [randint(0,100000) for i in range(10000)]
  43.  
  44. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
  45. bs = lambda: bubble_sort(list_to_sort)
  46. ms = lambda: merge_sort(list_to_sort)
  47. ts = lambda: sorted(list_to_sort)
  48.  
  49. #time the functions for 100 runs each
  50. print("Merge took:")
  51. print(timeit(ms, number = 100))
  52.  
  53. print("Bubble took:")
  54. print(timeit(bs, number = 100))
  55.  
  56. print("Timsort took:")
  57. print(timeit(ts, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement