Searching and sorting
Table of Contents
This assignment is to be done individually. You can talk to other people in the class, me (Dave), the prefect, and lab assistants for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn't hand a printout of your program to others. See the course syllabus for more details or just ask me if I can clarify.
We will use anonymous grading on Moodle, which means that the grader won't see your name until after the grading is done. This is an easy way to help add an extra element of fairness to the grading. Therefore, make sure your name doesn't appear on your actual submission. When you submit via Moodle, it will know you are. Thanks!
You can use whatever software you like to create this document, but you should submit it as a PDF. This is good practice for transmitting electronic work: sending word processor documents (such as Microsoft Word, etc) does not guarantee that your reader will see the layout in the same way that you do. Ask for help if you need help generating a PDF; you will lose a point if you do not do so.
1 Linear vs. binary search
When measuring the worst case performance of sequential and binary search, we did so by counting the number of times we compared the key against data in the list. Why didn't we do something simpler, like measuring running time with a stopwatch?
2 Key comparisons
In the case of quantifying how much work binary search takes, there's actually a subtle distinction between
- counting "the number of times we see if the key matches an item in the list," and
- counting "the number of times we compare our key against an item in the list."
Explain precisely how the answer you would get for your worst-case count in the second case differs from the first case. What criteria would make sense to use in deciding which of these two counts would be better to use?
3 Bubble sort
Here is a list of numbers:
[12, 6, 3, 9, 10, 4]
Show how bubble sort would handle this list. Specifically, show what the list would look like each time the positions of two numbers are changed.
Update on Fri May 25: I intentionally changed my mind to not cover bubble sort in class, since it's not in our departmental curriculum for CS 111 and I was having more fun giving a preview of merge sort. This bubble sort problem is now in the "last point" category; if you want to figure it out, go for it. There are lots of resources out there that describe how bubble sort works.
4 Insertion sort
Redo the above problem for insertion sort.
5 Selection sort
Redo the above problem for selection sort.