SHARE
TWEET

Prog102 - Bubble_merge_sorted( )

SteveJeff Aug 25th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from timeit import timeit
  2. from random import randint
  3.  
  4. ##################################################################
  5. # COPY AND PASTE YOUR bubble_sort AND merge_sort functions below #
  6. ##################################################################
  7.  
  8. def bubble_sort(unsorted):
  9.     sorted = unsorted[:]
  10.     changed = True
  11.     while changed:
  12.         changed = False
  13.         for i in range(len(sorted) - 1):
  14.             if sorted[i] > sorted[i+1]:
  15.                 sorted[i], sorted[i+1] = sorted[i+1], sorted[i]
  16.                 changed = True
  17.                
  18.     return sorted
  19.  
  20.  
  21. def merge(list_a, list_b):
  22.     list_c = []
  23.     while len(list_a) > 0  and len(list_b) > 0:
  24.         if list_a[0] < list_b[0]:
  25.             list_c.append(list_a.pop(0))
  26.         else:
  27.             list_c.append(list_b.pop(0))
  28.     if list_a == []:
  29.         list_c += list_b
  30.     else:
  31.         list_c += list_a
  32.     #print("merged list is", list_c)
  33.     return list_c
  34.  
  35.  
  36. def merge_sort(unsorted):
  37.     if len(unsorted) < 2:
  38.         return unsorted
  39.     else:
  40.         middle = len(unsorted) // 2
  41.         front = unsorted[:middle]
  42.         back = unsorted[middle:]
  43.         #print("splits are", front, back)
  44.         front = merge_sort(front)
  45.         back = merge_sort(back)
  46.     return merge(front, back)
  47.  
  48.  
  49.  
  50. #Generate a large (1000 items) random list
  51. list_to_sort = [randint(0,100000) for i in range(1000)]
  52.  
  53. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
  54. bs = lambda: bubble_sort(list_to_sort)
  55. ms = lambda: merge_sort(list_to_sort)
  56. tim_s = lambda: sorted(list_to_sort)
  57.  
  58. #time the functions for 100 runs each
  59. print("Merge took:")
  60. print(timeit(ms, number = 100))
  61.  
  62. print("Bubble took:")
  63. print(timeit(bs, number = 100))
  64.  
  65. print("Tim Sort took:")
  66. print(timeit(tim_s, number = 100))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top