Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from timeit import timeit
- from random import randint
- ##################################################################
- # COPY AND PASTE YOUR bubble_sort AND merge_sort functions below #
- ##################################################################
- ### BUBBLE Sort
- def bubble_sort(unsorted):
- ### MAKE COPY OF ORIGINAL LIST ###
- original_list = list_to_sort[:]
- swapped = True
- while swapped:
- swapped = False
- for i in range(len(unsorted) - 1):
- if unsorted[i] > unsorted[i+1]:
- unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i]
- swapped = True
- ### MERGE Sort
- def merge(list_a, list_b):
- list_sorted = []
- while list_a != [] and list_b != []:
- if list_a[0] < list_b[0]:
- list_sorted.append(list_a.pop(0))
- else:
- list_sorted.append(list_b.pop(0))
- if len(list_a) < 1:
- list_sorted += list_b
- else:
- list_sorted += list_a
- return list_sorted
- def merge_sort(unsorted):
- if len(unsorted) <= 1:
- return unsorted
- else:
- middle = len(unsorted) // 2 # rounding down if the list has an odd number of items
- front = unsorted[:middle]
- back = unsorted[middle:]
- front = merge_sort(front)
- back = merge_sort(back)
- return merge(front, back)
- #Generate a large (10 items) random list
- list_to_sort = [randint(0,100000) for i in range(1000)]
- #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
- bs = lambda: bubble_sort(list_to_sort)
- ms = lambda: merge_sort(list_to_sort)
- #time the functions for 100 runs each
- print("Merge took:")
- print(timeit(ms, number = 100))
- print("Bubble took:")
- print(timeit(bs, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement