Advertisement
makispaiktis

Comparing execution times of sorting methods

Apr 1st, 2020 (edited)
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.74 KB | None | 0 0
  1. def bubble_sort(A):
  2.     n = len(A)
  3.     for j in range(0, n-1):
  4.         for i in range(j+1, n):
  5.             if A[i] > A[j]:
  6.                 A[i], A[j] = A[j], A[i]
  7.  
  8.  
  9. def insertion_sort(A, p=None, r=None):
  10.     if p is None:
  11.         p = 0
  12.     if r is None:
  13.         r = len(A)-p
  14.     for j in range(p+1, r):
  15.         key = A[j]
  16.         i = j - 1
  17.         while i >= p and A[i] > key:
  18.             A[i + 1] = A[i]
  19.             i = i - 1
  20.         A[i + 1] = key
  21.  
  22. def merge_sort(A, p=None, r=None):
  23.     if p is None:
  24.         p = 0
  25.     if r is None:
  26.         r = len(A)-1-p
  27.     if p < r:
  28.         q = (p + r) // 2
  29.         merge_sort (A, p, q)
  30.         merge_sort (A, q + 1, r)
  31.         merge(A, p, q + 1, r)
  32.  
  33. def merge(A, p, q, r):
  34.     n1 = q - p
  35.     n2 = r - q + 1
  36.  
  37.     L = []
  38.     R = []
  39.     for i in range(0, n1):
  40.         L.append(A[p + i])
  41.     for j in range(0, n2):
  42.         R.append(A[q + j])
  43.     L.append(float("inf"))
  44.     R.append(float("inf"))
  45.  
  46.     i = 0
  47.     j = 0
  48.     for k in range(p, r + 1):
  49.         if L[i] <= R[j]:
  50.             A[k] = L[i]
  51.             i = i + 1
  52.         else:
  53.             A[k] = R[j]
  54.             j = j + 1
  55.  
  56.  
  57. # EXECUTION TIME
  58. # MAIN FUNCTION
  59. from timeit import default_timer as timer
  60. import random
  61. import matplotlib.pyplot as plt
  62.  
  63. def time(sort_alg, node_range=None):
  64.     if node_range is None:
  65.         node_range = range(10, 510, 10)
  66.     times = []
  67.     for n in node_range:
  68.         A = [random.random() for _ in range(n)]
  69.         start = timer()
  70.         sort_alg(A) # run sorting algorithm
  71.         times.append(timer()-start) # add time difference to time
  72.     plt.plot(node_range, times, label=sort_alg.__name__)
  73.  
  74. time(merge_sort)
  75. time(insertion_sort)
  76. time(bubble_sort)
  77. plt.legend()
  78. plt.show()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement