Assignment #5 - PQSort Comparison

Objectives:

The main objectives of this assignment are:
• Developing timing tests for more complex algorithms
• Improve our understanding of sorting algorithms and big-O notation
• Better comprehension of O(n²) vs. O(n lg n) time.

The Assignment:

We will be timing some specific operations and measuring their performance on PQSort using the three differing PQ implementations (Sorted, Unsorted, and Heap). We will then graph the performance as the data size (n) increases.

Testing

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.

Remember that timing can be tricky for a variety of reasons. For this assignment we will design tests and collect samples until a minimum amount of time has elapsed. Pay attention to the following guidelines:

• The following pseudo-code describes the basic technique for constructing a test sequence:

       Algorithm: makeRandomTest
       Input: n - the number of elements in the random test sequence
       Output: s - a sequence of n random numbers in the range 0 to 100,000
       // Create the test sequence:
       Sequence s = new Sequence()
       java.util.Random random = new java.util.Random();
       // Initialize the Sequence:
       for i=0 to n-1
          s.addLast(random.nextInt(100000));
     

  Create a separate method to generate each type of sequence.

• A "timing" test should be performed repeatedly for each sample case until a sufficient amount of time has elapsed. The following pseudo-code describes a basic algorithm for the timing tests:

       Algorithm: testInsertionSort
       Input: s - a sequence to use for empirical measurement of insertion
                  sort
       Input: minimum time - the minimum amount of time to run tests
       Output: average time taken
       
       System.gc()          // Force java to Garbage Collect
       samples=0            // No samples yet  
       start = current time // Begin stopwatch
       do {
          insertionSort(s)  // Sort the data
          
          samples++        
          stop = current time
       } while(stop-start < minimum time);
       average time = (stop-start)/(1.0*samples)
       return average time
     

  For this project use a minimum time of 500,000 nanoseconds (1/2 s).

Tests & Questions

1. Read through (but don't yet implement) the following experiments:
   1. A comparison of the three sorting techniques on Random data. For each sort (Unordered, Ordered, and Heap). For each of the following sizes, create a random sequence and run timing test on all three sorts using the same sequence. n=10,25,50,100,1000, 2000,4000,8000,16000, 32000, 64000, 128000, 256000.

      This will give you a total of 39 "times", 13 for each sort. You will need to plot 3 lines, one for each sort, so be sure that the data is stored or displayed in a way that makes this easy. For example, something like

                    System.out.printf("%4d , %7.5f , %7.5f , %7.5f %n", n, selectionTime, insertionTime, heapTime);
                    

      will allow you to import the columns of data into a spreadsheet as a "comma separated value" (CSV) file.
   2. A comparison of the three sorting techniques on Ordered data. For each sort (Unordered, Ordered, and Heap). For each of the following sizes, create an ordered sequence (0, 1, 2, 3, ..., n-1) and run timing test on all three sorts using the same sequence. n=10,25,50,100,1000, 2000,4000,8000,16000, 32000, 64000, 128000, 256000.

      Again, you will give you a total of 39 "times", 13 for each sort.

   3. A comparison of the three sorting techniques on Reverse ordered data. For each sort (Unordered, Ordered, and Heap). For each of the following sizes, create a reverse ordered sequence (n-1, n-2, ..., 1, 0) and run timing test on all three sorts using the same sequence. n=10,25,50,100,1000, 2000,4000,8000,16000, 32000, 64000, 128000, 256000.

      Again, you will give you a total of 39 "times", 13 for each sort.

   4. A comparison of the three sorting techniques on mostly sorted data. For each sort (Unordered, Ordered, and Heap). For each of the following sizes, create an ordered sequence (0, 1, 2, 3, ..., n-1), and swap 10% of the data randomly. Then run timing test on all three sorts using the same sequence. n=10,25,50,100,1000, 2000,4000,8000,16000, 32000, 64000, 128000, 256000.

      Example: 10% of n=50 is 5:

                    for i=0 to 5
                      pick random location 1
                      pick random location 2
                      swap the data between 1 and 2
                    

      Again, you will give you a total of 39 "times", 13 for each sort.

2. For each of the four tests run, create a line graphs showing the performance of all three sorts:
   • The horizontal (x) axis should be "Sequence Size (n)"
   • The vertical axis (y) should be "Time (in ms)"
   • The title should be "PQ Sorting Times vs. Sequence Size for X Data", where the X is either "Random", "Ordered" "Reverse Ordered", or "Mostly Ordered"
   • Be sure it's an X-Y plot, with linear axes for both X and Y.
   • Include a legend that clearly indicates which line represents which sort.
3. Based on your big-O analysis of the operations draw a sketch of what you expect each graph to look like. You don't need to include units, but estimate the shape of lines in each graph. This will be included with your homework. It is important that you do this before implementing your tests and performing measurements.
4. Implement the tests, perform the measurements, and produce the required graphs.
5. Answer the following questions:
   1. Did your empirical tests match what you expected from analysis (sketches)?
   2. What, if anything, surprised you about the results?
   3. What are the advantages or disadvantages of each type of sort?
   4. Why is there such a large difference in the variance when the big-O is the same?
   5. Which of the sorting algorithms would you use for small data sets (< 100)? What about large data sets (> 10,000)?
   6. Did you learn anything interesting from this assignment?
6. For bonus credit you may also implement all three sorts in-place. If you do this, submit your in-place version of the sorts as well, run the same tests with the in-place version, and answer the following questions. With the in-place sort you should have an integer array as the argument (instead of a Sequence) and you should create a clone of the array right before sending it to the sorting algorithm. This should be done immediately prior to the tests within the timing loop. Include the in-place lines on each of the four graphs. (Each graph will show 6 lines)
   7. Did the in-place version perform better?
   8. What about in terms of big-O?
   9. Are there ways to optimize the time even more?

Submission:

A typed report with clear graphs is due in the CS Office (221 Rekhi) before 5pm on the date listed.

Consider the following checklist:

1. Are the sketched version of all four graphs included?
2. Are the post-testing version of all four graphs included?
3. Just to double check, do you have 8 graphs total (4 sketches and 4 printed graphs)?
4. Does each graph have three lines? (6 for bonus credit)?
5. Are all the questions answered?
6. Do the graphs match what was requested?
7. Are you displaying AVERAGE times (elapsed/samples) rather than the TOTAL times (elapsed)?
8. Are the horizontal and vertical axis linear?
9. Are the horizontal and vertical axis labeled?
10. Are the horizontal and vertical axis correct?
11. Do the graphs have titles?
12. Are lines clearly marked and easy to read?
13. Is all work neat and legible? (The grader will not grade work that is hard to read)

Grading Criteria:

• Sketches of expected results: 20 points
• Graphs showing actual results: 60 points
• Answers to questions: 20 points
• Bonus points for submitting and graphing in-place sorts: 25 points