This is a zip file for the programming tutorial.

CSPB3104 Programming Assignment 1 solved

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment || To Order Original Work Click Custom Order?

Description

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_compares

Complexity 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 them

Merge 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 them

Quick 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 wish

Complexity 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 them

Testing 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

Related products