SortswithTimings

Dec 27th, 2020
824
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #
2. from timeit import timeit
3. from random import randint
4.
5. def merge(list1, list2):  #  assumption here is list 1 and list 2 is sorted
6.     list_sorted = []  # an empty list to add the sorted items
7.     while list1 !=[] and list2 != []: # keep looping while bot lists are not empty
8.         if list1[0] < list2[0]: # checking is list1 is the smallest if it is
9.             list_sorted.append(list1.pop(0)) # append it to list sorted and remove it
10.         else:
11.             list_sorted.append(list2.pop(0)) # if not smallest item is in list 2 to add that to the sorted list and remove it
12.     if len(list1)<1:  # while loop breaks if one list is empty, if it list1
13.         list_sorted += list2 # add list2 to the sorted list
14.     else:
15.         list_sorted += list1 # else it means list1 has data so that has to be added to the sorted list
16.     return list_sorted  ##could we use list 2 instead??
17.
18. a = [2,5,7,9,12,45,234,1900]
19. b = [1,4,6,8,9]
20. # [1, 2, 4, 5, 6, 7, 8, 9, 9, 12, 45, 234, 1900]
21.
22. #print(merge(a,b))
23.
24. def merge_sort(unsorted):
25.     #print(unsorted)
26.     if len(unsorted) <=1: #  has the list got 1 or less than one elements
27.         return unsorted # it's sorted
28.     else:
29.         middle = int(len(unsorted) / 2) # rounds down if odd number
30.         front = merge_sort(unsorted[:middle]) # split out the front part)
31.         back = merge_sort(unsorted[middle:]) # and no the back part
32.         #print(front, back)
33.     return merge(front, back)
34.
35. def bubblesort(unsorted):
36.     my_sorted_list = unsorted[:]
37.     swapped = True
38.     while swapped:
39.         swapped = False
40.         for i in range(len(my_sorted_list)-1):
41.             if my_sorted_list[i] > my_sorted_list[i+1]:
42.                 my_sorted_list[i], my_sorted_list[i+1] = my_sorted_list[i +1], my_sorted_list[i]
43.                 swapped = True
44.         #print(my_sorted_list)
45.
46. #c=[20, 15,6,4,20]
47. #Generate a large (1000 items) random list
48. list_to_sort = ([randint(0,100000) for i in range(10)])
49.
50. # list_to_sort = [2674, 3120, 5911, 8147, 9192, 9702, 9714, 11511, 11572, 12092, 13451, 13453, 15418, 16565, 17627, 17785, 18858, 19049, 21750, 22668, 24164, 26367, 26486, 27013, 27182, 27479, 29819, 31372, 31611, 33560, 33968, 34125, 34496, 35104, 36569, 38053, 38669, 40038, 40498, 40598, 40955, 41011, 41608, 42607, 43306, 44277, 44454, 44674, 45246, 46185, 48490, 49361, 51108, 52358, 53998, 55862, 56081, 56590, 58293, 59160, 61034, 61094, 61348, 61458, 61955, 62512, 63155, 63320, 64268, 66897, 67455, 68039, 69213, 69970, 71596, 74814, 75375, 75495, 75806, 78562, 80422, 80909,  85979, 89025,83456, 85166, 89038, 90272, 90885, 91317, 92006, 93843, 94069, 96714, 97328, 96261, 96697,  97404, 98384, 99061]
51.
52. #Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
53. bs = lambda: bubblesort(list_to_sort)
54. ms = lambda: merge_sort(list_to_sort)
55. ts = lambda: sorted(list_to_sort)
56.
57. #print(merge_sort(c))
58.
59. #time the functions for 100 runs each
60. print("Merge took:")
61. print(timeit(ms, number = 100))
62.
63. print("Bubble took:")
64. print(timeit(bs, number = 100))
65.
66. print("Timsort took:")
67. print(timeit(ts, number = 100))