Advertisement
earlution

compare_bubble_insertion_sort_execution_time.py

Dec 1st, 2022
651
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.74 KB | None | 0 0
  1. import random
  2. import time
  3.  
  4. def generate_randonised_list(length):
  5.     # generate a list containing 1000 values (0-999)
  6.     rand_list = list()
  7.     for x in range(length):
  8.         rand_list.append(x)
  9.  
  10.     # randomly sort generated list
  11.     random.shuffle(rand_list)
  12.  
  13.     return rand_list
  14.  
  15.  
  16. # source: https://www.geeksforgeeks.org/bubble-sort/
  17. def insertion_sort(arr):
  18.  
  19.     # Traverse through 1 to len(arr)
  20.     for i in range(1, len(arr)):
  21.  
  22.         key = arr[i]
  23.  
  24.         # Move elements of arr[0..i-1], that are
  25.         # greater than key, to one position ahead
  26.         # of their current position
  27.         j = i-1
  28.         while j >= 0 and key < arr[j] :
  29.                 arr[j + 1] = arr[j]
  30.                 j -= 1
  31.         arr[j + 1] = key
  32.  
  33.     return arr
  34.  
  35.  
  36. # source: https://www.geeksforgeeks.org/bubble-sort/
  37. def bubble_sort(arr):
  38.     n = len(arr)
  39.  
  40.     # Traverse through all array elements
  41.     for i in range(n):
  42.  
  43.         # Last i elements are already in place
  44.         for j in range(0, n-i-1):
  45.  
  46.             # traverse the array from 0 to n-i-1
  47.             # Swap if the element found is greater
  48.             # than the next element
  49.             if arr[j] > arr[j+1]:
  50.                 arr[j], arr[j+1] = arr[j+1], arr[j]
  51.  
  52.     return arr
  53.  
  54.  
  55. def main(list_length):
  56.     randomised_list_1 = generate_randonised_list(list_length)
  57.     randomised_list_2 = randomised_list_1.copy()
  58.    
  59.     start_time = time.time()
  60.     insertion_sort(randomised_list_1)
  61.     end_time = time.time()
  62.     print('Insertion sort execution time:', end_time - start_time, 'seconds')
  63.  
  64.     start_time = time.time()
  65.     bubble_sort(randomised_list_2)
  66.     end_time = time.time()
  67.     print('Bubble sort execution time:', end_time - start_time, 'seconds')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement