Advertisement
zhongnaomi

bubble sort and merge sort timeit

Feb 13th, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.68 KB | None | 0 0
  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(sorted):
  9.     n = len(sorted)  
  10.     while (n >= 1 ) :
  11.         newn = 0
  12.         for i in range(1, len(sorted)):
  13.            
  14.             if sorted[i-1] > sorted[i]:
  15.                 sorted[i-1], sorted[i] = sorted[i], sorted[i-1]
  16.                 newn = i
  17.         n = newn
  18.      return sorted      
  19.            
  20.            
  21.  
  22. def merge(list_a, list_b):
  23.     list_c = []
  24.     while len(list_a) > 0  and len(list_b) > 0:
  25.         if list_a[0] < list_b[0]:
  26.             list_c.append(list_a.pop(0))
  27.         else:
  28.             list_c.append(list_b.pop(0))
  29.     if list_a == []:
  30.         list_c += list_b
  31.     else:
  32.         list_c += list_a
  33.    
  34.     return list_c
  35.  
  36.  
  37. def merge_sort(unsorted):
  38.     if len(unsorted) < 2:
  39.         return unsorted
  40.     else:
  41.         middle = len(unsorted) // 2
  42.         front = unsorted[:middle]
  43.         back = unsorted[middle:]
  44.        
  45.         front = merge_sort(front)
  46.         back = merge_sort(back)
  47.     return merge(front, back)
  48.  
  49.  
  50.  
  51. ##################################################################
  52.  
  53.  
  54.  
  55. #Generate a large (1000 items) random list
  56. list_to_sort = [randint(0,100000) for i in range(1000)]
  57.  
  58. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
  59. bs = lambda: bubble_sort(list_to_sort)
  60. ms = lambda: merge_sort(list_to_sort)
  61.  
  62. #time the functions for 100 runs each
  63. print("Merge took:")
  64. print(timeit(ms, number = 100))
  65.  
  66. print("Bubble took:")
  67. print(timeit(bs, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement