CSC212 Lab 12 2014

--D. Thiebaut (talk) 19:37, 9 November 2014 (EST)

---

This lab deals with Sorting algorithms, HeapSort, QuickSort, and methods used to avoid worst-case conditions.

Lab Problem #1: Recursion-Stack Depth

• Create a class containing the code for Quicksort.
• Run it on arrays of size 10, 200, 500, 1000, 5000, 10000, 50000, 100000. Keep on increasing the size until something happens...
• You probably ran into an exception... Make sure you read what the exception is... Can you figure it out?
• Read the documentation of the -XSS command line on this page.
• Apply it to your program

• If you are using Eclipse, click on the Run top menu-option, then Run Configurations, then on the Arguments tab, and in the VM arguments window, enter something like -Xss64m (you'll have to do go through some trials and errors to find the right value.

* If you are running your Java code on beowulf, simply add the option on the command line:

    java -Xss64m QuickSort 1000000 random

• Make sure you have define a large enough stack to sort at least a million ints.

Lab Problem #2: HeapSort

• Java provides heap data structures, but calls them PriorityQueues.
• Instead of keeping the largest element at the top of the heap, PriorityQueues keep the smallest element at the top.
• Try the example below to see how to use a PriorityQueue

        import java.util.PriorityQueue;
	
	public static void TestPrioQueues() {

		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

		heap.add( 1 );
		heap.add( 20 );
		heap.add( 5 );
		heap.add( 100 );
		while ( ! heap.isEmpty() )
			System.out.println( heap.poll() );
	}

Question 1

Using some of the code/functions from this page, create a function called heapsort( int[] A ) that will use a priority queue to sort the array of ints A.

Question 2

Using the code snippet below, measure the execution times of QuickSort and of your HeapSort function. Figure out which is regularly faster on arrays of varying sizes.

        long start = System.nanoTime();
        quicksort(A, 0, A.length - 1);
        long end   = System.nanoTime();
        System.out.println( String.format(   
                                "quickSort( %d ) takes %1.3f msec", N,
                               (end-start)/1000000.0f ) );

Lab Problem #3: Speeding Up QuickSort

• You should have gone through Problem #2 and modified QuickSort so that you can measure its execution time.
• Name your file Lab12_3.java, and your class Lab12_3 (you will need to submit it to Moodle).
• Run it on sorted arrays of varying sizes until you find an array size that requires between 1 and 10 seconds of execution time.
• Pick one of the methods we saw in class for allowing Quicksort to avoid worst case conditions, and implement it. Modify your code.
• Verify that you have seriously improved your Quicksort function with this mod.

Moodle Submission

• Submit your program to Moodle. Your program will be run against the solution program on a sorted array. The grade is proportional to how close your execution time comes to the execution time of the solution program.