Advertisement
zhongnaomi

two merge sort timing

Feb 13th, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.09 KB | None | 0 0
  1. from timeit import timeit
  2. from random import randint
  3.  
  4. ##################################################################
  5.  
  6.  
  7. # teacher's merge sort
  8. def merge1(list_a, list_b):
  9.     list_c = []
  10.     while len(list_a) > 0  and len(list_b) > 0:
  11.         if list_a[0] < list_b[0]:
  12.             list_c.append(list_a.pop(0))
  13.         else:
  14.             list_c.append(list_b.pop(0))
  15.     if list_a == []:
  16.         list_c += list_b
  17.     else:
  18.         list_c += list_a
  19.    
  20.     return list_c
  21.  
  22.  
  23. def merge_sort1(unsorted):
  24.     if len(unsorted) < 2:
  25.         return unsorted
  26.     else:
  27.         middle = len(unsorted) // 2
  28.         front = unsorted[:middle]
  29.         back = unsorted[middle:]
  30.        
  31.         front = merge_sort1(front)
  32.         back = merge_sort1(back)
  33.     return merge1(front, back)
  34.            
  35.            
  36. # the other  merge sort          
  37.  
  38. def merge(list_a, list_b):
  39.     list_c = []
  40.     while len(list_a) > 0  and len(list_b) > 0:
  41.         if list_a[0] < list_b[0]:
  42.             list_c.append(list_a.pop(0))
  43.         else:
  44.             list_c.append(list_b.pop(0))
  45.     if list_a == []:
  46.         list_c += list_b
  47.     else:
  48.         list_c += list_a
  49.    
  50.     return list_c
  51.  
  52.  
  53. def merge_sort(unsorted):
  54.     if len(unsorted) <=1:
  55.         return unsorted
  56.     front =[]
  57.     back =[]
  58.    
  59.     for i,x in enumerate(unsorted,start=0):
  60.        
  61.         if i < len(unsorted)/2:
  62.             front.append(x)
  63.         else:
  64.             back.append(x)
  65.            
  66.    
  67.     front = merge_sort(front)
  68.     back = merge_sort(back)
  69.     return merge(front, back)
  70.  
  71.  
  72.  
  73. ##################################################################
  74.  
  75.  
  76.  
  77. #Generate a large (1000 items) random list
  78. list_to_sort = [randint(0,100000) for i in range(1000)]
  79.  
  80. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
  81. bs = lambda: merge_sort1(list_to_sort)
  82. ms = lambda: merge_sort(list_to_sort)
  83.  
  84. #time the functions for 100 runs each
  85. print("My Merge took:")
  86. print(timeit(ms, number = 100))
  87.  
  88. print("teacher's merge sort  took:")
  89. print(timeit(bs, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement