• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?