SHARE
TWEET

Untitled

a guest Aug 19th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def merge(list_a, list_b):
  2.   list_sorted = []
  3.   while list_a and list_b:
  4.     if list_a[0] < list_b[0]:
  5.       list_sorted.append(list_a.pop(0))
  6.     else:
  7.       list_sorted.append(list_b.pop(0))
  8.   if list_a:
  9.     list_sorted += list_a
  10.   else:
  11.     list_sorted += list_b
  12.   return list_sorted
  13.  
  14. def merge_sort(unsorted):
  15.   # unsorted is a list
  16.   length = len(unsorted)
  17.   if length <= 1:
  18.     return unsorted
  19.   middle = length//2
  20.   front = merge_sort(unsorted[:middle])
  21.   back = merge_sort(unsorted[middle:])
  22.   return merge(front, back)
  23.  
  24. def bubble_sort(unsorted):
  25.   sorted = unsorted[:]  # copy the unsorted list
  26.   ran = range(len(sorted)-1)
  27.   swapped = True
  28.   while swapped:
  29.     swapped = False
  30.     for i in ran:
  31.       # compare items with indices i and i+1:
  32.       if sorted[i] > sorted[i+1]:
  33.         sorted[i], sorted[i+1] = sorted[i+1], sorted[i]
  34.         swapped = True
  35.   return sorted
  36.  
  37. from timeit import timeit # requires Python 3!
  38. from random import randint
  39.  
  40. # Create anonymous functions to use with timeit:
  41. bs = lambda: bubble_sort(list_to_sort)
  42. ms = lambda: merge_sort(list_to_sort)
  43. ts = lambda: sorted(list_to_sort)
  44.  
  45. for i in range(1,4):
  46.   n = 10**i
  47.   # Generate a large (n items) random list
  48.   list_to_sort = [randint(0,100000) for i in range(n)]
  49.   list_to_sort = sorted(list_to_sort)
  50.  
  51.   # Time the functions for 100 runs each
  52.   print("Timsort of {} items took:".format(n))
  53.   print(timeit(ts, number = 100))
  54.  
  55.   print("Merge_sort of {} items took:".format(n))
  56.   print(timeit(ms, number = 100))
  57.  
  58.   print("Bubble_sort of {} items took:".format(n))
  59.   print(timeit(bs, 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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top