CS 303e, Assignment #8: Sorting Algorithms Due: Sunday, March 31, 2019
Points: 20
Purpose: The purpose of this project is for you to become familiar with the various sorting algorithms in computer science and big-o notation. In this assignment you will be practicing: writing functions, looping, conditionals, if statements, and lists.
Learning Objectives: By the end of this assignment you should be able to:-Design and code a variety of functions
-Decide what parameters are needed in a given situation
-Design a small Python program
-Practice writing a Python program from a written description
-Practice with the logistics of common sort algorithms
-Practice with lists
-Practice finding and using outside resources and reading programming documentation
Background:
As we discussed in class, there are three common / basic sort algorithms: selection, insertion, and bubble. All three of these algorithms have the same worst-case time complexity / big-o. Generally, sort algorithms are written to sort values from smallest to largest, but can be modified for reverse order.
The Assignment:
1. Code a version of the selection sort that puts the numbers in reverse order. (Biggest to
smallest)
Code a version of the insertion sort that puts the numbers in reverse order. (Biggest to
smallest)
Code a version of the bubble sort that puts the numbers in reverse order. (Biggest to
smallest)
Rules:
-You must have at least 4 functions (one for each sort algorithm and a main)
- You cannot use any built-in sorts or reverse of a list or string. The reverse must be in the
sorting algorithm itself(using any of these built-in with cause you to receive a 0 for the
entire assignment)
- If you find code on the Internet for the sorting algorithms you must credit where you got it.Failure to credit any of the code will cause you to receive a 0 for the entire assignment.
Input and Output:
Inputwill be a bunch of numbers separated by a single space (i.e., 54 26 17 93)Outputwill the sort type and the list of numbers in the correct order (i.e., [93, 54, 26, 17])
Sample Format of Input and Output:
Enter numbers to be sorted:54 26 17 93Selection sort = [93, 54, 26, 17]
Insertion sort = [93, 54, 26, 17]
Bubble sort = [93, 54, 26, 17]
Create a python file that contains three functions (one for each sort algorithm). You can assume that the input will be in the correct form and only contain numbers. (Hint: Use the split method to get all the numbers from the input line to a list).
Submission Instructions:
•In order to receive full credit, you must submit a .py file (otherwise your assignment cannot
be graded and will result in a 0) to Canvas
•Assignments are not submitted via email. (Even late assignments)
•If your assignment is late, the penalty is 5% per day. (This includes weekends, holidays, etc).•Make sure you submit the correct file (submitting the incorrect file results in a 0)
The Auto-Grader:
Yes, a computer program will be grading your program! We will be using the Python
3 standard. (Please note: there are some differences between 2 and 3 - make sure
you have Python 3)
Your output must match exactly to earn full credit
When your output does not match exactly, you will temporarily be assigned a grade
of 0
Your assignment will be hand checked by the graders and your will earn partial
credit (see rubric below)
Please do not email us regarding your grade until after we announce (via
Canvas) finalized grades have be posted!
If we have announced grades have been finalized and you still have a zero or
other questions regarding your score,please see or contact the TA who posted the grades to discuss your grade (check Piazza for the announcements)
As stated in the syllabus:You haveone weekfrom when grades have been posted to contest the grade
Rubric (Total 15 points):
Correctly write each function: 4 functions, 3 points each = 12 points Correctly ask user for information and display information: 3 points Correctly sort from biggest to shortest: 5 points