Assessment Description
PART 1: ALGORITHMS
In this individual work, you will implement sorting algorithms and then test their performance. This part of the assignment consists of not just coding, but also testing your code and providing evidence. Note that when your code is complete, you still have a reasonable amount of work to do -- so start early!
Storing and Sorting Items
Consider a manufacturing company, XYZ that runs 24 hours and 7 days operational. The company produces a very large number of items per week. In a week from Monday to Sunday, it produces 20, 300, 4000, 50000, 75000, 100000 and 500000 items, respectively. Each item has a random integer identifier.
You are expected to create an Integer ArrayList and store the item IDs for each day of the week – so you will have 7 different ArrayList storing items accordingly. Now, you are required to randomly generate item IDs from 1000 to 600000 for each day as stated above.
Now think about the logic of applying the Quicksort algorithm and first write its pseudocode. Once you’re done, convert your pseudocode into a Java code and run your code successfully.
Efficiency Testing
Once you have implemented your algorithm, you need to test it to see how long your sorting algorithm takes to run. You should test the speed of the algorithm on all three: random, sorted and reverse-sorted lists. You are expected to use System.currentTimeMillis() to estimate the execution time. Using currentTimeMillis only gives an accurate time estimate if the function takes a long time to run (at least a couple of seconds). Run your code a number of times and compute the average time, print the output screenshot and discuss in the report -- reflect how many iterations are sufficient to provide an accurate time of the algorithm.
Developing a Better Sorting Algorithm
Quicksort is faster when the number of items to be sorted in a list is large. But when lists are small enough, quicksort runs slower than some of the Θ(n2) algorithms.
If you carefully notice, each time the quicksort method is recursively called, the sublist to be sorted could be either small or large. The time to sort one small sublist with a faster algorithm can be negligible. However, sorting such hundreds of small sublists can make a difference in the overall efficiency of the sort.
Here, you will combine Quicksort with another sorting algorithm to create the fastest possible sorting algorithm. We call this “hybrid Quicksort”. You have several options --
· Use Quicksort until the sublist gets “small enough”, and then use selection sort to sort the small lists.
· Use Quicksort until the sublist gets “small enough”, and then use insertion sort to sort the small lists.
· Use Quicksort to "mostly" sort the list, i.e., use the Quicksort to sort any sublists larger than a cut-off size, and then stop. The list will now be mostly sorted, and you can use selection sort on the entire list to quickly complete the sorting.
· Use Quicksort to "mostly" sort the list, i.e., use the Quicksort to sort any sublists larger than a cut-off size, and then stop. The list will now be mostly sorted, and you can use insertion sort on the entire list to quickly complete the sorting.
· Use some other method of your own devising.
What does “small enough” mean? You can try a percentage of the list (say, 5% or 10%), or an absolute number (8, 10, 15, 100 elements, etc.), or something else of your choice. What does “mostly” sort mean? A cut-off size of the items to be sorted in the list.
You should test your choices to ensure that you have the most efficient algorithm possible. You should also be sure that your hybrid Quicksort has reasonable performance on all lists: sorted and inverse sorted lists as well as random lists. Try various methods for choosing the pivot element, to try to get the best possible behaviour.
You need to complete the following tasks and submit them electronically:
Q1-A. Source code for your hybrid sorting algorithm sorting all items in the ArrayLists for the week and performing efficiency testing for sorted and inverse sorted lists as well as random lists for each list size in these tests. [20 marks]
Q1-B. Write a 1000-word (maximum) explanation of how you developed your hybrid sorting algorithm, what combinations of the algorithms/approaches you tried, what different parameters you chose, and how much of a difference these changes made to the efficiency of your algorithm, including the run time complexity. [30 marks]
Create a single report (.doc or .pdf) file containing the following:
(i) Screenshot of the final output for efficiency testing from Q1-A. Make sure your hybrid quicksort has reasonable performance on all lists, sorted and inverse sorted lists as well as random lists for each list size.
(ii) Your explanation for Q1-B above.
It is okay for you to discuss solutions to Part-1 with your classmates. However, no collaboration should ever involve looking at one of your classmate's source codes. It is usually fairly easy to determine that someone has copied a code, even when the individual copying the code has changed identifier names and comments.
Assessment Criteria
Credit will be awarded against the following criteria.
PART 1:
High Distinction (80%+) –[Q1-A] Fully working codes that demonstrate an excellent understanding of the assignment problem and scenarios using a relevant Java approach. Excellent formatting of input/output, catch exception handling, the application deals well with invalid user input and doesn’t crash for any data. Excellent and consistent code layout. Appropriate use of comments. [Q1-B] All required outputs. Clear, concise, reflective and appropriate write-up with all justified choices.
Distinction (70-79%) –[Q1-A] Fully working codes that demonstrate a very good understanding of the assignment problem and scenarios using a relevant Java approach. Very good formatting of input/output, catch exception handling, the application deals well with invalid user input and doesn’t crash for any data. Very good and consistent code layout. Appropriate use of comments. [Q1-B] All required outputs. Clear and appropriate write-up with all justified choices.
Merit (60-69%) – [Q1-A] All required functionalities of the codes are met (with no runtime error) demonstrating a good understanding of the assignment problem and scenarios using a relevant Java approach. Good formatting of input/output, catch exception handling, the application may have a few errors with invalid user input. Good and consistent code layout. Good use of comments. [Q1-B] Most of the required outputs are presented. Clear and suitable write-up with mostly justified choices.
Pass (50-59%) –[Q1-A] Some required functionalities of the codes are met (with only minor errors) demonstrating some understanding of the assignment problem and scenarios using a relevant Java approach. Some formatting of input/output, catch exception handling, the application may have some errors with invalid user input. Some and partially consistent code layout. Some use of comments. [Q1-B] Only some required outputs. Some write-up with partially justified choices.
Marginal Fail (40-49%) - [Q1-A] Faulty codes with wrong implementation (with major errors), partially demonstrating the understanding of the assignment problem and scenarios using a relevant Java approach. Bad formatting of input/output, catch exception handling, the application has major errors with invalid user input. Modest and inconsistent code layout. poor use of comments. [Q1-B] Only a few required outputs. Partially clear and rough write-up with poorly justified choices.
Fail (0-39%) - [Q1-A] Faulty codes with incorrect implementation (code does not run), poorly demonstrating the understanding of the assignment problem and scenarios using a relevant Java approach. Poor formatting of input/output, catch exception handling, the application has major errors with invalid user input, and crashes with most data. Poor and inconsistent code layout. No use of comments. [Q1-B] No or only a few required outputs. Unclear and poor write-up with no justified choices.