![[SOLVED] Cspb3104 programming assignment 1](https://assignmentchef.com/wp-content/uploads/2022/08/downloadzip.jpg)
5/5 – (1 vote)
Goal:
This programming assignment will ask you to do the following tasks.
(a) Implement some of the sorting algorithms for sorting integer data in ascending order in python3.
- Simple sort (implemented for you)
- Bubble Sort (read from book or online sources)
- Merge Sort
- Quicksort
(b) Your implementation must count the number of compare operations each sorting algorithm carries out.
(c) You must formulate a series of arrays of lengths from 55 to 100100 (step by 5), that will form the worst case of these sorting algorithms and plot the number of comparisons in the worst case vs. size of input array (x axis)
(d) Generate 10001000 random inputs for each size and compute average time. Plot the size of input array (x axis) vs. number of comparisons (y axis)
Simple Sort
%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
def simple_sort(a):
# must sort the array a in place and return the number of comparisons
num_compare = 0
n = len(a)
for i in range(0, n): # i goes from 0 to n-1
for j in range(i+1, n): # j goes from i+1 to n-1
num_compare = num_compare + 1
if a[i] >= a[j]:
# swap
a[i], a[j] = a[j], a[i]
return num_compare# TESTING CODE
a = [3, 10, 1, 29, -1, 4, 3, 15, 2, -2]
nc = simple_sort(a)
print('Num Comparison = ', nc)
print('Sorted Result = ', a)Num Comparison = 45 Sorted Result = [-2, -1, 1, 2, 3, 3, 4, 10, 15, 29]
Complexity analysis of simple sort.
Note that simple sort consists of two loops and regardless of the input array, the first loop runs from n steps. And the second loop runs n−i−1n−i−1 steps where ii is the index of the first loop. Thus, the worst case, best case and average case complexity should be ∑n−1j=1j=n(n−1)2∑j=1n−1j=n(n−1)2 comparisons = Θ(n2)Θ(n2)
The code below plots it for arrays of size 5, 10, …, 100. However, we cannot really distinguish between the number of comparisons for randomized vs. worst case.
import random
# CODE TO GENERATE WORST CASE
array_sizes = range(5, 100, 5)
# Code for creating an already sorted array
def create_ascending_sorted_array(a_size):
a = []
for i in range(a_size):
a.append(i)
return a
# Code for creating a random array
def create_random_shuffled_array(a_size):
a = list(range(a_size))
random.shuffle(a)
return a
# Code for running sorting and generating number of compares
num_compares_wc = []
for n in array_sizes:
a = create_ascending_sorted_array(n)
nc = simple_sort(a)
num_compares_wc.append(nc)
# Randomized comparisons
num_compares_random = []
num_trials = 1000
for n in array_sizes:
total = 0
for m in range(num_trials):
a = create_random_shuffled_array(n)
nc = simple_sort(a)
total = total + nc
avg = total / num_trials
num_compares_random.append(avg)
# Code for plotting
plt.plot(array_sizes, num_compares_wc, label='Worst Case')
plt.plot(array_sizes, num_compares_random, label='Average Case')
plt.legend(['Worst Case', 'Average Case'])
plt.title('Simple Sort (Worst and Average Cases)')
plt.xlabel('Array Size')
plt.ylabel('Number of Comparisons')
plt.show()
Bubble Sort
def bubble_sort(a):
# Implement code to bubble sort the given array a in place.
# Also return the number of comparisons.
num_compares = 0
# ... blah blah blah ..
return num_comparesComplexity Analysis of Bubble Sort
__Todo: explain what the worst and average cases are. Explain how you would craft inputs for the worst case __
## WRITE CODE HERE TO GENERATE WORST CASE and AVERAGE CASE INPUTS/PLOT
## You may cut and paste from code we provided or directly call themMerge Sort
def merge_sort(a):
# Implement the code for merge sort
# Use a function merge_sort_recursive to implement the recursive call
# Be careful in counting number of comparisons since you should include comparisons in the merge part.
# Also: code needs to sort the array a. You may have to copy things over from a temp array back into a.
return merge_sort_recursive(a, 0, len(a)-1)Complexity Analysis of Merge Sort
__Todo: explain what the worst and average cases are. Explain how you would craft inputs for the worst case __
## WRITE CODE HERE TO GENERATE WORST CASE and AVERAGE CASE INPUTS/PLOT
## You may cut and paste from code we provided or directly call themQuick Sort
def quick_sort(a):
# Implement code for quick sort
# Must sort the array a in place
# Must return the number of comparisons
return # you can implement it how you wishComplexity Analysis of Quick Sort
__Todo: explain what the worst and average cases are. Explain how you would craft inputs for the worst case __
## WRITE CODE HERE TO GENERATE WORST CASE and AVERAGE CASE INPUTS/PLOT
## You may cut and paste from code we provided or directly call themTesting Code: Do not edit
def test_sorting_algorithm(sort_fun, sz, num_trials):
num_passed = 0
for i in range(num_trials):
a = create_random_shuffled_array(sz)
a_orig = list(a) # make a copy
b = sorted(a)
nc = sort_fun(a)
if a == b:
num_passed = num_passed + 1
else:
print('----')
print('FAILED: Input = ', a_orig)
print('Expected: ', b)
print('Obtained:', a)
print('----')
print('Num Trials = ', num_trials)
print('Num Passed = ', num_passed)test_sorting_algorithm(simple_sort, 50, 100)Num Trials = 100 Num Passed = 100
test_sorting_algorithm(bubble_sort, 10, 10)---- FAILED: Input = [9, 8, 5, 4, 3, 6, 7, 1, 0, 2] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [9, 8, 5, 4, 3, 6, 7, 1, 0, 2] ---- ---- FAILED: Input = [3, 9, 8, 4, 0, 5, 6, 2, 7, 1] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [3, 9, 8, 4, 0, 5, 6, 2, 7, 1] ---- ---- FAILED: Input = [1, 6, 8, 2, 4, 0, 7, 5, 9, 3] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [1, 6, 8, 2, 4, 0, 7, 5, 9, 3] ---- ---- FAILED: Input = [5, 9, 2, 7, 0, 8, 4, 6, 3, 1] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [5, 9, 2, 7, 0, 8, 4, 6, 3, 1] ---- ---- FAILED: Input = [3, 2, 0, 8, 5, 9, 6, 4, 7, 1] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [3, 2, 0, 8, 5, 9, 6, 4, 7, 1] ---- ---- FAILED: Input = [0, 2, 1, 9, 8, 6, 4, 7, 3, 5] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [0, 2, 1, 9, 8, 6, 4, 7, 3, 5] ---- ---- FAILED: Input = [0, 6, 3, 1, 9, 7, 5, 2, 4, 8] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [0, 6, 3, 1, 9, 7, 5, 2, 4, 8] ---- ---- FAILED: Input = [7, 3, 5, 4, 9, 6, 0, 1, 8, 2] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [7, 3, 5, 4, 9, 6, 0, 1, 8, 2] ---- ---- FAILED: Input = [5, 9, 4, 8, 6, 1, 7, 3, 0, 2] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [5, 9, 4, 8, 6, 1, 7, 3, 0, 2] ---- ---- FAILED: Input = [2, 1, 4, 0, 5, 7, 3, 9, 8, 6] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [2, 1, 4, 0, 5, 7, 3, 9, 8, 6] ---- Num Trials = 10 Num Passed = 0
test_sorting_algorithm(merge_sort, 10, 10)---------------------------------------------------------------------------
NameError Traceback (most recent call last)
<ipython-input-28-9e06f1dd96aa> in <module>()
----> 1 test_sorting_algorithm(merge_sort, 10, 10)
<ipython-input-23-15703f38a571> in test_sorting_algorithm(sort_fun, sz, num_trials)
5 a_orig = list(a) # make a copy
6 b = sorted(a)
----> 7 nc = sort_fun(a)
8 if a == b:
9 num_passed = num_passed + 1
<ipython-input-20-2c2d7a21f43e> in merge_sort(a)
4 # Be careful in counting number of comparisons since you should include comparisons in the merge part.
5 # Also: code needs to sort the array a. You may have to copy things over from a temp array back into a.
----> 6 return merge_sort_recursive(a, 0, len(a)-1)
NameError: name 'merge_sort_recursive' is not defined
test_sorting_algorithm(quick_sort, 10, 10)---- FAILED: Input = [1, 7, 0, 8, 5, 2, 9, 4, 3, 6] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [1, 7, 0, 8, 5, 2, 9, 4, 3, 6] ---- ---- FAILED: Input = [7, 8, 6, 2, 9, 4, 1, 3, 5, 0] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [7, 8, 6, 2, 9, 4, 1, 3, 5, 0] ---- ---- FAILED: Input = [4, 6, 7, 0, 2, 1, 3, 9, 5, 8] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [4, 6, 7, 0, 2, 1, 3, 9, 5, 8] ---- ---- FAILED: Input = [4, 7, 5, 1, 2, 0, 8, 9, 6, 3] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [4, 7, 5, 1, 2, 0, 8, 9, 6, 3] ---- ---- FAILED: Input = [2, 5, 7, 4, 9, 6, 1, 0, 8, 3] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [2, 5, 7, 4, 9, 6, 1, 0, 8, 3] ---- ---- FAILED: Input = [1, 7, 9, 4, 0, 3, 6, 5, 2, 8] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [1, 7, 9, 4, 0, 3, 6, 5, 2, 8] ---- ---- FAILED: Input = [8, 9, 7, 5, 2, 1, 0, 4, 3, 6] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [8, 9, 7, 5, 2, 1, 0, 4, 3, 6] ---- ---- FAILED: Input = [2, 5, 6, 9, 1, 3, 0, 8, 4, 7] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [2, 5, 6, 9, 1, 3, 0, 8, 4, 7] ---- ---- FAILED: Input = [7, 6, 5, 0, 3, 1, 9, 2, 8, 4] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [7, 6, 5, 0, 3, 1, 9, 2, 8, 4] ---- ---- FAILED: Input = [5, 1, 6, 9, 7, 3, 4, 2, 8, 0] Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Obtained: [5, 1, 6, 9, 7, 3, 4, 2, 8, 0] ---- Num Trials = 10 Num Passed = 0
Reviews
There are no reviews yet.