Topic: Searching and Sorting Algorithms, and their implementations in Python
Related Reading: Sections 7.4-7.6, class notes, and Prof. Goldwasser's notes on Python
For some of the problems in this assignment, you will need to use Python. You can either use a Python run-time environment, such as available on the Mac computers in RH 225 (or the Linux computers in RH 121), or you can use the Python simulation environment, as desired.
Experiment with the Python implementations of the various search algorithms:
Experiment with the Python implementations of the various sorting algorithms:
Consider the following sorted list of numbers:
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 2 | 4 | 7 | 10 | 13 | 16 | 17 | 20 | 24 | 28 | 31 | 38 | 41 | 43 | 45 |
What sequence of 'middle' values are compared to the target when performing a binary search with target 28?
What sequence of 'middle' values are compared to the target when performing a binary search with target 16?
What sequence of 'middle' values are compared to the target when performing a binary search with target 5?
Note: The solution for the above questions can be found by running a Binary Search Demonstration with parameter "#items: 15" and "seed: 15849" and with the target "key" value set appropriately.
When you turn in your assignment, you must include a signed cover sheet with your assignment (you're assignment will not be graded without a completed cover sheet).
You are allowed to submit your assignment via email, but if you choose to do so, you must bring a hardcopy of your assignment along with a completed cover sheet to the instructor at the next class. (Note: Do not email the instructor any .zip file attachments, as SLU's email may not accept these emails, i.e. the instructor may not receive your email.)
Using the following sorted list of words to perform a binary search:
| index | value |
|---|---|
| 0 | babka |
| 1 | baklava |
| 2 | cheesecake |
| 3 | cupcake |
| 4 | danish |
| 5 | eclair |
| 6 | funnelcake |
| 7 | kringle |
| 8 | lamington |
| 9 | profiterole |
| 10 | sopaipilla |
| 11 | strudel |
| 12 | tiramisu |
| 13 | torte |
| 14 | turnover |
What sequence of 'middle' values are compared to the target when performing a binary search with target doughnut?
What sequence of 'middle' values are compared to the target when performing a binary search with target tiramisu?
In the book in Sections 7.4-7.6, the authors discuss the Selection Sort, Bubble Sort, and Quicksort sorting algorithms. When discussing the Quicksort algorithm (in Section 7.6), they use the following list to demonstrate how the first pass of the Quicksort algorithm operates:
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| value | 9 | 20 | 6 | 10 | 14 | 8 | 60 | 11 |
Using this same list, do the following:
Show the series of steps taken by the Bubble Sort algorithm while sorting this list.
Show the series of steps taken by the Selection Sort algorithm while sorting this list.
The book, in Section 7.4, shows the series of steps taken during the first pass of sorting the list. In particular, Figure 7.16 on p. 231 shows the steps taken to determine the split point, and then p. 229 shows how the split point splits the list into two halves (Note: halves do not need to be equal-sized). Once the list is split in two, the Quicksort algorithm is applied again to each half, so it is applied to the sub-list, [6, 8], and the sub-list, [10, 14, 20, 60, 11]. It does not need to sort the split point, 9, any further, since it's final position is now known.
Show all the remaining steps (i.e. the second and subsequent passes) performed by the Quicksort algorithm to complete the sorting of the list..
As discussed in class, the three search algorithms have varying run times, with the unsorted sequential search being the least efficient and the binary search being the most efficient (among the three). This problem will illustrate the execution time differences by measuring the number of elements that are checked in the array when searching for the search string.
First, you need to instrument the code (i.e. make a minor addition to the code) for each of the algorithms in order to count the number of elements in the array that are checked during a search.
In order to do this, you will need to add a count variable to the function implementing the search algorithm. You will want to initialize this count to zero at the beginning of the function, add 1 to it each time it checks a new distinct element of the list to see if it is the search value, and finally prints out the count at the end of the function.
Modify the code for the unsorted sequential search and the sorted sequential search to count the number of elements checked during the search.
Note 1: You only need to add 3 lines of code to the search procedure in each case!
Note 2: Since the initial versions of the sorted and unsorted sequential search are searching for strings, you will need to change the user query for input to convert the input to a number. In other words, you will need to change this line:
searchVal = raw_input("What name do you want to search for? ")
to
searchVal = int(raw_input("What number do you want to search for? "))
We have provided the instrumented code for the binary search with counting since the modifications to that search algoritm are much more complicated.
Using your instrumented code for the three search algorithms, perform the following searches, and report the number of elements checked by each algorithm for each search (i.e. you will report nine results in total -- for each of the 3 searches below, you will report the results from the 3 different search algorithms).
A = [6, 19, -3, 5, 12, 7, 21, -8, 25, 10, 0, 28, -6, 1, 33, 18, 9, 2, -13, 43]
A = [6, 19, -3, 5, 12, 7, 21, -8, 25, 10, 0, 28, -6, 1, 33, 18, 9, 2, -13, 43]
A = [6, 19, -3, 5, 12, 7, 21, -8, 25, 10, 0, 28, -6, 1, 33, 18, 9, 2, -13, 43, -15, 4, 22, 38, -5, 13, 23, -11, 29, -20, 41, 31, -23, 35, 40, 14, 8, -18, 16, 36]