Divide and Conquer
Important: Do individually (each student alone is NOT a group assignment), each student has to turn in a java program.
Quicksort
Implement the simplest version of the quicksort algorithm by choosing as pivot:
1. the last element
2. the median (randomized select algorithm)
3. [extra points] the median (deterministic select algorithm, median of medians)
Count the time and the number of comparisons for this version when sorting an array of random generated numbers and display the totals. Test it with large random generated arrays (10,000 - 100 million).
Use a very simple test driver that runs all two quicksort algorithms on a large array of randomly chosen integers and then verifies that the result is in order. What other practical improvements can you add? Your output should have something that looks like the following total runtime measurements for arrays of various sizes:
|
Array size
|
10,000
|
100,000
|
1,000,000
|
10,000,000
|
100,000,000
|
|
Total time (s) of QS1
|
|
|
|
|
|
|
Total time (s) of QS2
|
|
|
|
|
|
|
Comparisons in QS1
|
|
|
|
|
|
|
Comparisons in QS2
|
|
|
|
|
|
Sample Test class
public class QuickSortTest
{
public static void main(String[] args)
{
int maxSize = SIZE; // array size
int[] arr=...// create array
arr.quickSort1(); // quicksort version 1 arr.quickSort2(); // quicksort version 2
...
}
}
Note: To count the time use system.currentTimeMillis(). Every time you compare a pair of numbers increase an appropriate counter. The first programming assignment is basically to learn JUnit testing.
Attachment:- QuicksortTest.rar