.

SIT221 Data Structures and Algorithms Practical Task 3.3

Practical Task 3.3

This task is an extension of Task 3.1. Here, the aim is to learn the implementation of the two recursive sorting  algorithms: Merge Sort and Quick Sort.

1. Explore the program code attached to this task. Extend the project inherited from Task 3.1. Import the  Tester.cs file to the project to access the prepared Main method important for the purpose of debugging  and testing the required algorithmic solutions. 

2. Proceed with the implementation of the three sorting algorithms: Randomized Quick Sort, the top‐down version and the bottom‐up version of the Merge Sort. For this purpose, create three new classes, i.e. RandomizedQuickSort, MergeSortTopDown, and MergeSortBottomUp, respectively. Ensure that the new classes implement the ISorter interface along with its prescribed method Sort<K>. Each classNamemust have a default constructor. You may add any extra private methods and attributes if necessary.

3. First, start with the Randomized Quick Sort algorithm. The corresponding method must select the pivot element uniformly at random from a range of elements available within a recursive call. Furthermore, it must perform sorting operations “in‐place”. 

To get more insights about these particular requirements, and the Randomized Quick Sort in general, explore the material of Chapter 7 of SIT221 Workbook. Though it explains the algorithm, the pivot point selection used there follows the “median three” policy. As your aim is the random choice policy, peruse Chapter 12.2 of the SIT221 course book entitled “Data structures and algorithms in Java”. You should focus on Section 12.2.2 covering the in‐place version of the algorithm and Pseudocode 12.6 as this is one that you must encode. Selecting pivot points at random is explained in 12.1.1. This technique must replace line 7 of Pseudocode 12.6 with a randomized selection function. As you need to generate random numbers, use the standard Random classNameavailable within the .NET Framework.

4. Second, proceed with the top‐down version of the Merge Sort algorithm. 

5. Finally, complete the task by encoding the bottom‐up version of the Merge Sort. 

6. As you progress with the implementation of the algorithms, you should start using the Tester classNamein order to test them for potential logical issues and runtime errors. This (testing) part of the task is as important as coding. You may wish to extend it with extra test cases to be sure that your solutions are checked against other potential mistakes. To enable the tests, remember to uncomment the corresponding code lines. Remember that you may change the sorting approach for an instance of the Vector<T> classNameby referring its Sorter property to a new instance of that algorithm. For example, 

 vector.Sorter = new MergeSortTopDown(); 

should enable the top‐down Merge Sort algorithm encoded in the MergeSortTopDown className. Check whether you test the right algorithm. 

Expected Printout 

This section displays the printout produced by the attached Tester className, specifically by its Main method. It is based on our solution. The printout is provided here to help with testing your code for potential logical errors. It demonstrates the correct logic rather than an expected printout in terms of text and alignment.

Test A: Sort integer numbers applying RandomizedQuickSort with AscendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test B: Sort integer numbers applying RandomizedQuickSort with DescendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS

Test C: Sort integer numbers applying RandomizedQuickSort with OddNumberFirstComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [724,596,958,752,120,122,966,772,722,100,780,312,236,213,995,263,175,299,511,333]

:: SUCCESS

Test D: Sort integer numbers applying MergeSortTopDown with AscendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test E: Sort integer numbers applying MergeSortTopDown with DescendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS

Test F: Sort integer numbers applying MergeSortTopDown with OddNumberFirstComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [724,596,958,752,120,122,966,772,722,100,780,312,236,213,995,263,175,299,511,333]

:: SUCCESS

Test G: Sort integer numbers applying MergeSortBottomUp with AscendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test H: Sort integer numbers applying MergeSortBottomUp with DescendingIntComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS

Test I: Sort integer numbers applying MergeSortBottomUp with OddNumberFirstComparer:

Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]

Resulting order: [724,596,958,752,120,122,966,772,722,100,780,312,236,213,995,263,175,299,511,333] 

:: SUCCESS 

.