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

Top