Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def bubble_sort(A):
- n = len(A)
- for j in range(0, n-1):
- for i in range(j+1, n):
- if A[i] > A[j]:
- A[i], A[j] = A[j], A[i]
- def insertion_sort(A, p=None, r=None):
- if p is None:
- p = 0
- if r is None:
- r = len(A)-p
- for j in range(p+1, r):
- key = A[j]
- i = j - 1
- while i >= p and A[i] > key:
- A[i + 1] = A[i]
- i = i - 1
- A[i + 1] = key
- def merge_sort(A, p=None, r=None):
- if p is None:
- p = 0
- if r is None:
- r = len(A)-1-p
- if p < r:
- q = (p + r) // 2
- merge_sort (A, p, q)
- merge_sort (A, q + 1, r)
- merge(A, p, q + 1, r)
- def merge(A, p, q, r):
- n1 = q - p
- n2 = r - q + 1
- L = []
- R = []
- for i in range(0, n1):
- L.append(A[p + i])
- for j in range(0, n2):
- R.append(A[q + j])
- L.append(float("inf"))
- R.append(float("inf"))
- i = 0
- j = 0
- for k in range(p, r + 1):
- if L[i] <= R[j]:
- A[k] = L[i]
- i = i + 1
- else:
- A[k] = R[j]
- j = j + 1
- # EXECUTION TIME
- # MAIN FUNCTION
- from timeit import default_timer as timer
- import random
- import matplotlib.pyplot as plt
- def time(sort_alg, node_range=None):
- if node_range is None:
- node_range = range(10, 510, 10)
- times = []
- for n in node_range:
- A = [random.random() for _ in range(n)]
- start = timer()
- sort_alg(A) # run sorting algorithm
- times.append(timer()-start) # add time difference to time
- plt.plot(node_range, times, label=sort_alg.__name__)
- time(merge_sort)
- time(insertion_sort)
- time(bubble_sort)
- plt.legend()
- plt.show()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement