Task 1
Inside the task1 package in the starter code, you will find the following files:
.
├── ArrayIndexedList.java # from HW2
├── IndexedList.java # from HW2
├── MysterySort.java
└── SortingAlgorithm.java # from HW3
Open the MysterySort.java file. As the name suggests, this file contains the implementation of a sorting algorithm that shall remain nameless! Feel free to run the sortSample test in SortingAlgorithmTest in debug mode and investigate how the MysterySort works!
Open the README.md file. Under the section about "Mystery Sort", complete the following table. Each pass through the mystery sort corresponds to one complete iteration of the do-while loop in its implementation.
| Indices | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] |
|---|---|---|---|---|---|---|---|---|
| Input | $14$ | $10$ | $23$ | $34$ | $6$ | $17$ | $50$ | $14$ |
| 1st pass | ||||||||
| 2nd pass |
The above exercise will assist you in better understanding how the MysterySort works. Next, in the same README.md file, under the designated section, describe (briefly) the strategy (algorithm) behind the mystery sort. (One or two paragraphs at most.) Elaborate on its asymptotic runtime and space complexity in the best and worst cases. Make sure to note what are the best/worse case scenarios for the mystery sort.
Describe the algorithm not the code! For example, do not write "we declare boolean variable
swapped$\dots$"