CSC $204-$ Algorithm Design & Analysis

Extra Credit $1-$ Insertion Sort

Instructions:

Implement the insertion sort algorithm based off the pseudo$-$code provided in lecture. You

must implement the algorithm in python. I have provided a file, insertion$\_$sort.py in which

you will write all of your code.

Use your implemented insertion sort function to simulate the running times for three

separate cases $-$ best case $($already sorted$),$ worst case $($reversely sorted$),$ average case

$($random order$).$ For each case, vary the input size and create a line plot where the x$-$axis is

the input size $(n)$ and the y $-$axis is the time in microseconds. Show all plots in the same

graph.

Write a few sentences describing what you see in your plot and why.

Grading:

If you hand in this assignment you will earn either an extra credit of $2\%$ on your final grade or

nothing at all. In order to receive the $2\%$ your implementation of insertion sort must pass all

test cases, your plot must sufficiently and clearly demonstrate the running time differences

between all three cases, and the explanation you provide must adequately explain the results

in the plot. If any of these requirements are not met than you will not receive any credit.

What to turn in:

On canvas please turn in the following two files

insertion$\_$sort.py which should include your insertion sort algorithm as well as any code

used to simulate your algorithm and generate your plot.

analysis.pdf which should include your $\text{'}\text{'}\text{'}$

Extra Credit $1-$ Insertion Sort

Name:

Hofstra ID:

def insertion$\_$sort$($arr$)$:

$\text{'}\text{'}\text{'}$

sorts an array using the insertion sort

algorithm

Parameters:

arr $($list$)$: a list of integers

pass

def generate$\_$running$\_$time$\_$plot$()$:

$\text{'}\text{'},$

generates plot demonstrating running time

difference between

best case

worst case

average $($random$)$ case

$\text{'}\text{'}\text{'}$

pass

if $\_\_\_$ name$\_\_==\text{'}\text{'}$ :

passplot and your explanation of your plot.