Advertisement
timber101

SortswithTimings

Dec 27th, 2020
824
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.10 KB | None
  1. #
  2. from timeit import timeit
  3. from random import randint
  4.  
  5. def merge(list1, list2):  #  assumption here is list 1 and list 2 is sorted
  6.     list_sorted = []  # an empty list to add the sorted items
  7.     while list1 !=[] and list2 != []: # keep looping while bot lists are not empty
  8.         if list1[0] < list2[0]: # checking is list1 is the smallest if it is
  9.             list_sorted.append(list1.pop(0)) # append it to list sorted and remove it
  10.         else:
  11.             list_sorted.append(list2.pop(0)) # if not smallest item is in list 2 to add that to the sorted list and remove it
  12.     if len(list1)<1:  # while loop breaks if one list is empty, if it list1
  13.         list_sorted += list2 # add list2 to the sorted list
  14.     else:
  15.         list_sorted += list1 # else it means list1 has data so that has to be added to the sorted list
  16.     return list_sorted  ##could we use list 2 instead??
  17.    
  18. a = [2,5,7,9,12,45,234,1900]
  19. b = [1,4,6,8,9]
  20. # [1, 2, 4, 5, 6, 7, 8, 9, 9, 12, 45, 234, 1900]
  21.  
  22. #print(merge(a,b))
  23.  
  24. def merge_sort(unsorted):
  25.     #print(unsorted)
  26.     if len(unsorted) <=1: #  has the list got 1 or less than one elements
  27.         return unsorted # it's sorted
  28.     else:
  29.         middle = int(len(unsorted) / 2) # rounds down if odd number
  30.         front = merge_sort(unsorted[:middle]) # split out the front part)
  31.         back = merge_sort(unsorted[middle:]) # and no the back part
  32.         #print(front, back)
  33.     return merge(front, back)
  34.    
  35. def bubblesort(unsorted):
  36.     my_sorted_list = unsorted[:]
  37.     swapped = True
  38.     while swapped:
  39.         swapped = False
  40.         for i in range(len(my_sorted_list)-1):
  41.             if my_sorted_list[i] > my_sorted_list[i+1]:
  42.                 my_sorted_list[i], my_sorted_list[i+1] = my_sorted_list[i +1], my_sorted_list[i]
  43.                 swapped = True
  44.         #print(my_sorted_list)
  45.  
  46. #c=[20, 15,6,4,20]
  47. #Generate a large (1000 items) random list
  48. list_to_sort = ([randint(0,100000) for i in range(10)])
  49.  
  50. # list_to_sort = [2674, 3120, 5911, 8147, 9192, 9702, 9714, 11511, 11572, 12092, 13451, 13453, 15418, 16565, 17627, 17785, 18858, 19049, 21750, 22668, 24164, 26367, 26486, 27013, 27182, 27479, 29819, 31372, 31611, 33560, 33968, 34125, 34496, 35104, 36569, 38053, 38669, 40038, 40498, 40598, 40955, 41011, 41608, 42607, 43306, 44277, 44454, 44674, 45246, 46185, 48490, 49361, 51108, 52358, 53998, 55862, 56081, 56590, 58293, 59160, 61034, 61094, 61348, 61458, 61955, 62512, 63155, 63320, 64268, 66897, 67455, 68039, 69213, 69970, 71596, 74814, 75375, 75495, 75806, 78562, 80422, 80909,  85979, 89025,83456, 85166, 89038, 90272, 90885, 91317, 92006, 93843, 94069, 96714, 97328, 96261, 96697,  97404, 98384, 99061]
  51.  
  52. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
  53. bs = lambda: bubblesort(list_to_sort)
  54. ms = lambda: merge_sort(list_to_sort)
  55. ts = lambda: sorted(list_to_sort)
  56.  
  57. #print(merge_sort(c))
  58.  
  59. #time the functions for 100 runs each
  60. print("Merge took:")
  61. print(timeit(ms, number = 100))
  62.  
  63. print("Bubble took:")
  64. print(timeit(bs, number = 100))
  65.  
  66. print("Timsort took:")
  67. print(timeit(ts, number = 100))
Advertisement
RAW Paste Data Copied
Advertisement