Assignment 7: A Duel of Sorts

Due by: Friday, November 22, 2024 at 11:59 p.m.

Your mission, should you choose to accept it, is to implement four different sorting algorithms and time them. The algorithms are:

• Quicksort
• Heap sort
• Merge sort
• Radix sort

Specification

Create a class called Sorting in a file called Sorting.java. Add a method for each of the algorithms above, using the following signatures:

• public static void quickSort(int[] array, int start, int end)
• public static void mergeSort(int[] array, int[] scratch, int start, int end)
• public static void heapSort(int[] array)
• public static void radixSort(int[] array, int digits)

All sorting is to be done with int arrays, in ascending order. For quickSort() and mergeSort(), the start and end parameters specify the first element of the array and one past the last element of the array. Doing so allows you to make a direct call to the first of a series of recursive methods. To sort an array named values, you would call quickSort( values, 0, values.length ) or mergeSort( values, new int[values.length], 0, values.length ). (The immediately previous call to mergeSort() shows an easy way to pass an appropriately sized scratch array to mergeSort().) The digits value passed into radixSort() gives the maximum number of digits. For this assignment, you can always pass in 6.

In addition to the sorting methods, you must include a main() method that runs the four sorts on sizes of 10,000, 100,000, and 1,000,000 elements, respectively. Using a loop to iterate over sizes can allow you to avoid copying and pasting the same code three times. You must time how long it takes to sort each size of array. You must randomly generate numbers between 0 (inclusive) and 1,000,000 (exclusive) to populate these arrays. Note that this range allows you to consider only 6 digits with radix sort. Also, you must copy the elements of these arrays so that you are sorting exactly the same sequences of values for each of the four sorts. Use the System.nanoTime() method to record a starting time in nanoseconds. Then, use it again to record an ending time. Subtract the two and then divide by 1000000000.0 to get the time in seconds. Your output should look similar to the following, but random values and differences in implementation can make your times vary significantly from those listed below. Round your times to four digits after the decimal point using System.out.format().

Array length:		10000
Quicksort:		0.0019 seconds
Merge Sort:		0.0025 seconds
Heap Sort:		0.0026 seconds
Radix Sort:		0.0036 seconds

Array length:		100000
Quicksort:		0.0075 seconds
Merge Sort:		0.0124 seconds
Heap Sort:		0.0183 seconds
Radix Sort:		0.0174 seconds

Array length:		1000000
Quicksort:		0.0837 seconds
Merge Sort:		0.1255 seconds
Heap Sort:		0.1674 seconds
Radix Sort:		0.0621 seconds       

Hints

Make sure that you implement the algorithms specified. Refer to your notes, the book, my office hours, and Wikipedia if you need help with an algorithm.

You are permitted to implement additional helper methods. For example, you might want a partition() method for quickSort(), a merge() method for mergeSort(), or a bubbleDown() method for heapSort().

Since you are generating numbers in the range 0 to 1,000,000 (not counting 1,000,000), make sure you specify 6 digits when you call radixSort().

Make copies of your arrays so that you are sorting the same numbers. The Arrays.copyOf() method is a reasonable way to do this. Do not re-sort the same array over and over. Only measure the time it takes to sort, not the time to fill the arrays.

Use the counting and copying approach to radix sort, not the version that uses queues.

You should not import anything except for java.util.Random and java.util.Arrays (and that only for the copy).

Test your code thoroughly. Make sure your sorts actually work before timing them.

Turn In

Upload Sorting.java to Brightspace. Grace days are not available for assignments.

All work must be done individually. You may discuss general concepts with your classmates, but it is never acceptable for you to look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Under no circumstances should any student look at the code written by another student. Tools will be used to detect code similarity automatically.

Grading

There are four sorting methods specified above. The correctness of each is worth 20%, totaling 80%. The correctness and formatting of your timing output is worth an additional 20%. Be sure that you put your name, date, course number, and assignment number in comments at the top of your files. Failure to compile will result in a zero for the assignment.

If you implement Timsort as well, according to the specifications here, you can earn up to an additional 10% extra credit.