Mod $7$ Lab: Which sorting algorithm is which?

Differentiate $5$ sorting algorithms $($bubble$,$ selection, insertion, merge, and quick$)$ based on how long

they take to sort certain lists.

When you submit a file called numbers.txt to Gradescope, it will sort the numbers inside with these $5$

algorithms, aliased as alg$\_$a$,$ alg$\_$b$,$ alg$\_$c$,$ alg$\_$d$,$ and alg$\_$e:

$================$

n $=1000$

$----------------$

alg t $($ms$)$

$----------------$

alg$\_$a $24\mathrm{.}6$

alg$\_$b $1\mathrm{.}35$

alg$\_$c $57$

alg$\_$d $2\mathrm{.}12$

alg$\_$e $40\mathrm{.}1$

$----------------$

You need to

$1)$ Create lists of different lengths and patterns

$2)$ Determine which alias corresponds to which sorting algorithm

Answers

Write your answers in answers.py$.$ It contains a dictionary where the keys are the aliased algorithms; you

just need to enter the correct values $($bubble$,$selection$,$insertion$,$merge$,$ or $$quick$)$:

answers $=\{\text{'}$alg$\_$a$\text{'}$: $\text{'}\text{'},$ 'alg$\_$b$\text{'}$: $\text{'}\text{'},$ 'alg$\_$c$\text{'}$: $\text{'}\text{'},$ 'alg$\_$d$\text{'}$: $\text{'}\text{'},$ 'alg$\_$e$\text{'}$: $\text{'}\text{'}\}$

Lab Notes

$$ generate$\_$numbers.py contains code to automate the generation of numbers.txt$.$

$$ Each algorithm is used exactly once.

$$ The bubble and insertion sorts are adaptive $-$ they can sort in O$($n$)$ in the best case.

$$ The quicksort algorithm always uses the last element in a sublist as the pivot.

$$ The largest list you can create is $2000$ items due to resource constraints on Gradescope.

Submitting

Students must submit individually by the due date $($typically$,$ Sunday at $11$:$59$ pm EST$)$ to receive credit.

Grading

This assignment is entirely auto$-$graded: $20$ points per correct algorithm

code answers.py:

# Include your answers for this lab in the dictionary below.

# The keys of the dictionary are the pre$-$numbered algorithms.

# The values are your answers. Use:

# 'bubble'

# 'selction'

# 'insertion'

# 'merge'

# 'quick'

# #For instance, if you though all the algorithms were bubble sort $($they are not$),$ this file should read:

# answers $=\{\text{'}$alg$\_$a$\text{'}$: 'bubble',

# 'alg$\_$b$\text{'}$: 'bubble',

# 'alg$\_$c$\text{'}$: 'bubble',

# 'alg$\_$d$\text{'}$: 'bubble',

# 'alg$\_$e$\text{'}$: 'bubble'$\}$

# Fill in your answers as the values in the dict below

answers $=\{\text{'}$alg$\_$a$\text{'}$: $\text{'}\text{'},$

'alg$\_$b$\text{'}$: $\text{'}\text{'},$

'alg$\_$c$\text{'}$: $\text{'}\text{'},$

'alg$\_$d$\text{'}$: $\text{'}\text{'},$

'alg$\_$e$\text{'}$: $\text{'}\text{'}$

$\}$

valid$\_$ans $=\{\text{'}$bubble$\text{'},$ 'selection', 'insertion', 'merge', 'quick'$\}$

# Run this file in terminal to see if you used the correct formatting in your answer.

for k$,$ v in answers.items$()$:

if v not in valid$\_$ans:

raise ValueError$($f$"$Value $\text{'}\{$v$\}\text{'}$ for key $\text{'}\{$k$\}\text{'}$ is not in $\{$valid$\_$ans$\}")$

print$("$Valid answer! Find out if it's right after the due date."$)$

code generate$\_$numbers.py:

# This program generates a list of numbers and writes them to a file.

import random

##### Generate list of numbers #####

n $=1000$ # Max is $2000$ due to memory constraints with quicksort

L $=[$random$.$randint$(0,$ n$)$ for i in range$($n$)]$

##### Create file to write to #####

f $=$ open$($f$"./$numbers$.$txt$","$w$")$

##### Write numbers to file #####

for item in L:

f$.$write$($str$($item$))$

f$.$write$("")$

#### Close the file ####

f$.$close$()$

file name : numbers.txt