Instructions
Requirements and Specifications
Source Code
QUESTION 1
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()
QUESTION 2
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()
QUESTION 3
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()
QUESTION 4
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()