Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #
- from timeit import timeit
- from random import randint
- def merge(list1, list2): # assumption here is list 1 and list 2 is sorted
- list_sorted = [] # an empty list to add the sorted items
- while list1 !=[] and list2 != []: # keep looping while bot lists are not empty
- if list1[0] < list2[0]: # checking is list1 is the smallest if it is
- list_sorted.append(list1.pop(0)) # append it to list sorted and remove it
- else:
- list_sorted.append(list2.pop(0)) # if not smallest item is in list 2 to add that to the sorted list and remove it
- if len(list1)<1: # while loop breaks if one list is empty, if it list1
- list_sorted += list2 # add list2 to the sorted list
- else:
- list_sorted += list1 # else it means list1 has data so that has to be added to the sorted list
- return list_sorted ##could we use list 2 instead??
- a = [2,5,7,9,12,45,234,1900]
- b = [1,4,6,8,9]
- # [1, 2, 4, 5, 6, 7, 8, 9, 9, 12, 45, 234, 1900]
- #print(merge(a,b))
- def merge_sort(unsorted):
- #print(unsorted)
- if len(unsorted) <=1: # has the list got 1 or less than one elements
- return unsorted # it's sorted
- else:
- middle = int(len(unsorted) / 2) # rounds down if odd number
- front = merge_sort(unsorted[:middle]) # split out the front part)
- back = merge_sort(unsorted[middle:]) # and no the back part
- #print(front, back)
- return merge(front, back)
- def bubblesort(unsorted):
- my_sorted_list = unsorted[:]
- swapped = True
- while swapped:
- swapped = False
- for i in range(len(my_sorted_list)-1):
- if my_sorted_list[i] > my_sorted_list[i+1]:
- my_sorted_list[i], my_sorted_list[i+1] = my_sorted_list[i +1], my_sorted_list[i]
- swapped = True
- #print(my_sorted_list)
- #c=[20, 15,6,4,20]
- #Generate a large (1000 items) random list
- list_to_sort = ([randint(0,100000) for i in range(10)])
- # 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]
- #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
- bs = lambda: bubblesort(list_to_sort)
- ms = lambda: merge_sort(list_to_sort)
- ts = lambda: sorted(list_to_sort)
- #print(merge_sort(c))
- #time the functions for 100 runs each
- print("Merge took:")
- print(timeit(ms, number = 100))
- print("Bubble took:")
- print(timeit(bs, number = 100))
- print("Timsort took:")
- print(timeit(ts, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement