Assignment #4 - Sort Comparison
Objectives:
The main objectives of this assignment are:
- Implementing 5 and testing 8 sorting algorithms
- Improve our understanding of sorting algorithms and big-O notation
- Better comprehension of O(n2) vs. O(n lg n) time.
The Assignment:
The Concept:
This project is to implement different sorting algorithms and compare
their performance.
Your Job:
Implement the following sorting algorithms first and then run the time testing code the compare the performance of the above algorithms.
- InPlaceInsertionSort
- InPlaceSelectionSort
- InPlaceHeapSort
- PQsort (works with UnorderPQ, OrderedPQ and Heap PQ) - this has been
implemented for you
- QuickSort
- MergeSort
Geting Started
For this assignment, you don't need to download any zip file. Instead, you continue working on the project
that you have created for assignment3. The files that you need to complete are under cs2321/sorting.
Do not modify the following files under cs2321/sorting:
- Sorter.jave - Sorter interface
- HeapSort.java - PQSort with heap implementation of PQ
- InsertionSort.java - PQSort with Ordered list implementation of PQ
- SelectionSort.java - PQSort with Unordered list implementation of PQ
- PQSort.java
Here is the list of files that have unimplemented methods that you need to finish.
- InPlaceSelectionSort.java
- InPlaceInsertionSort.java
- InPlaceHeapSort.java
- QuickSort.java
- MergeSort.java
Time Testing
After implementing some sorting algorithm, you can test how long it will take
to sort 100,000 random number. See SortTiming.java for some basic testing
method.
As in Assignment 2, we will use System.nanoTime() for time measurement.
We'll also use the java.util.Random class to get a random number generator.
// Create the test array :
Integer[] arr = new Integer[100000];
java.util.Random random = new java.util.Random();
// generate random number and put them in the array
for(i=0; i < 100000; i++)
arr[i] = random.nextInt(100000));
Generate the random numbers, call one sorting algorithm to sort the random
100,000 numbers, record the time it takes. Repeat the procedure for each soring - there are total of 8 different sorting algorithm.
Create a bar graph of the time testing for all 8 sorting algorithms :
- The horizontal (x) axis should be sorting alg in the order of
QuickeSort,
MergeSort,
InPlaceHeapSort,
HeapSort,
InPlaceInsertionSort,
InPlaceSelectionSort,
InsertionSort:
SelectionSort:
- The vertical axis (y) should be "time in ms". ms = ns /1000000
- The title should be "The time to sort 100,000 data "
- Be sure it's a bar graph
Create another bar graph of the time testing for the fast four algorithms :
- The horizontal (x) axis should be sorting alg in the order of
QuickeSort,
MergeSort,
InPlaceHeapSort,
HeapSort
-
The vertical axis (y) should be "time in ms". ms = ns /1000000
- The title should be "The time to sort 100,000 data "
- Be sure it's a bar graph
Submission:
Export the PriorityQueuesWithSorts project and save it as prog4.zip, submit it.
Hand in the report with 2 graphs to CS office before the due date.
Grading Criteria:
- Sorting correctly: 60 points
- bar graph - Elapsed time in milli seconds (1ns =
1000000
ms) for sorting random 100,000
numbers. 16 points
- TA's check for appropriate implementation of each algorithm. If your implementation is wrong, for example, you use bubble sort in place of insertion sort, you will loose all points even you passed the test cases: -60points
- Time Complexity annotation: 16 points
- Comments and Style: 8 points
FAQ
- How to fix stack overflow error?
Change the eclipse java virtual machine stack size
Run -> Run configuration -> Auguments -> VM arguments
add -Xss12800k
Command line:
java -Xss12800k cs2321.sorting.SortTiming