CMPU 125: Lab 6

CMPU 125 Lab 6: Testing efficiency of sorting algorithms experimentally

This lab gives you some experience measuring the actual running time of algorithms.

Part 1:

Write a class called TestSorts that measures the performance of some common sorting algorithms. To wean yourselves from the acm package, you should not import any of the acm classes for this class.

You will need to take input from the user, and a convenient way to do this is to use the JOptionPane class methods. To use JOptionPanes, you will need to import the javax.swing package. To read an integer, use the following syntax:

int size = Integer.parseInt(JOptionPane.showInputDialog(null,
"Please enter the size of the array to be sorted."));

The null argument to the showInputDialog method could be replaced by a container name, but if no container is given, the dialog box will open by itself.

This class should contain

A main method to do the following:

Read integers for size and range from the user with JOptionPanes as described above.
Call the genRanArray method (described below) to generate an array of size unique random numbers between 0 and range. Use timing statements (described below) before and after the call to the genRanArray method to measure the amount of time your program takes to generate the array of unique numbers.
Call each of the five sorting algorithms mentioned in Part 2 on the same unsorted array generated in step 1.
Use timing statements to determine the system time used by each sorting algorithm on the array generated in step 1 and print the running time for each algorithm using System.out.println methods. Sample output is shown below.

A static method genRanArray that takes 2 integer input parameters, n and m, and returns an unsorted array containing m (pseudo) random integers between 1 and n. Use the Random class from the java.util package to generate the random integers. This class exports a nextInt method that takes an upper range as an input argument and generates a pseudo-random number between 0 and the upper range - 1. Instead of using the getInstance() method like you did for the acm RandomGenerator class, you create a new Random object and then use that object to generate the random integers
A static method printArray that can be used to print the contents of the randomly generated array as shown below (note: You probably do not want to use this method to print very large arrays.) The array shown below has a size of 50 and a range of 400. You can test this method from the interactions pane to make sure your random generator is working properly.

The array to be sorted: [346, 102, 164, 265, 43, 206, 203, 393, 117, 109, 25, 204, 103, 44, 221, 348, 240, 81, 92, 104, 385, 200, 139, 340, 180, 317, 138, 241, 19, 375, 331, 136, 182, 254, 303, 47, 157, 397, 220, 158, 102, 163, 204, 203, 331, 291, 36, 33, 91, 379]

To test your methods in the interactions pane of DrJava, type the following:

> int[] arr1 = TestSorts.genRanArray(400, 50)
> TestSorts.printArray(arr1)

The first line creates an array of 50 elements in the range 0 to 399 and the second line prints the array as shown above.

Part 2:

Download the Sorts.java file. This file contains methods for the following sorting algorithms: InsertionSort, SelectionSort, BubbleSort, MergeSort, and QuickSort.

Timing in Java

Like most high-level languages, Java provides a method to measure the running time of a program. The call to this method is as follows:

               System.currentTimeMillis();

The currentTimeMillis method returns an integer of type long, representing the current system time in milliseconds.

Time a particular statement by calling it in between two calls to System.currentTimeMillis() and then subtracting the difference between the times returned by those two calls.

Your output should be as follows:

      
    Generating 20000 random numbers took 44 ms.
    Bubble sort took 3713 ms.
    Insertion sort took 1319 ms.
    Merge sort took 6130 ms.
    Quicksort took 25 ms.
    Selection sort took 1593 ms.

Test your program on large enough data sets to give you an idea of how the running time of each program relates to the size of the data set (warning: generating too large a data set will take a very long time). Recommended maximum size = 20000.

Run your program for your lab instructor when you get it working.

Submit your L6 directory when you are finished and have tested your program.