Python Program to Create Timing Experiment Assignment Solution

import random

import time

def bubble_sort(array):

"""

Given an array (list of integers), sort it using bubble sort

"""

n = len(array) # size of array

# Loop through the elements

for i in range(n):

# Loop through the elements from 0 to n-i-1

for j in range(n-i-1):

if array[j] > array[j+1]: # the element on the left is higher than the element on the right

# swap

array[j], array[j+1] = array[j+1], array[j]

if __name__ == '__main__':

# Ask user for size of array

n = int(input("Enter size: "))

# Create array

array = list()

# Generate n random integers and fill array

for i in range(n):

array.append(random.randint(-100,100)) # between -100 and 100

# Print original array

print("Original Array", array)

# Sort

bubble_sort(array)

# Print sorted array

print("Sorted Array:", array)

input()

import random

import time

def selection_sort(array):

"""

Given an array (list of integers), sort it using selection sort

"""

n = len(array) # size of array

# Loop through the elements

for i in range(n):

# Loop through the elements from 0 to n-i-1

min_index = i

for j in range(i+1, n):

if array[min_index] > array[j]:

min_index = j

# Swap

array[i], array[min_index] = array[min_index], array[i]

if __name__ == '__main__':

# Ask user for size of array

n = int(input("Enter size: "))

# Create array

array = list()

# Generate n random integers and fill array

for i in range(n):

array.append(random.randint(-100,100)) # between -100 and 100

# Print original array

print("Original Array", array)

# Sort

selection_sort(array)

# Print sorted array

print("Sorted Array:", array)

input()

import random

import time

def bubble_sort(array):

"""

Given an array (list of integers), sort it using bubble sort

"""

n = len(array) # size of array

# Loop through the elements

for i in range(n):

# Loop through the elements from 0 to n-i-1

for j in range(n-i-1):

if array[j] > array[j+1]: # the element on the left is higher than the element on the right

# swap

array[j], array[j+1] = array[j+1], array[j]

if __name__ == '__main__':

# Create running_time variable

running_time = 0

# Ask user for size of array

n = int(input("Enter size: "))

# Variable to store the average running time

avg_time = 0

# Begin with simulation the process 1000 times

for _ in range(1000):

# Create array

array = list()

# Generate n random integers and fill array

for i in range(n):

array.append(random.randint(-100,100)) # between -100 and 100

# Record start time

start_time = time.time()

# Sort

bubble_sort(array)

# Record end time

end_time = time.time()

# Calculate running time and add to avg_time

running_time = (end_time-start_time)

avg_time += running_time

# Calculate avgerage running time

avg_time = avg_time / 1000.0

# Print

print("The average running time for Bubble Sort is: {:.4f} ms".format(avg_time*1000.0))

input()

import random

import time

def selection_sort(array):

"""

Given an array (list of integers), sort it using selection sort

"""

n = len(array) # size of array

# Loop through the elements

for i in range(n):

# Loop through the elements from 0 to n-i-1

min_index = i

for j in range(i+1, n):

if array[min_index] > array[j]:

min_index = j

# Swap

array[i], array[min_index] = array[min_index], array[i]

if __name__ == '__main__':

# Create running_time variable

running_time = 0

# Ask user for size of array

n = int(input("Enter size: "))

# Variable to store the average running time

avg_time = 0

# Begin with simulation the process 1000 times

for _ in range(1000):

# Create array

array = list()

# Generate n random integers and fill array

for i in range(n):

array.append(random.randint(-100,100)) # between -100 and 100

# Record start time

start_time = time.time()

# Sort

selection_sort(array)

# Record end time

end_time = time.time()

# Calculate running time and add to avg_time

running_time = (end_time-start_time)

avg_time += running_time

# Calculate avgerage running time

avg_time = avg_time / 1000.0

# Print

print("The average running time for Selection Sort is: {:.4f} ms".format(avg_time*1000.0))

input()