Advertisement
GCK

GCK/ bubble sort versus merge and timsort

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