Question

As a general r libraries provided by the authors of our text in algs4.jar. However, java.util.Arrays.sort(), should be used as indicated below ule for programming assignments for this class, you should feel free to use the Exercise Comparing Sorting Methods . The purpose of this exercise is to get a good feel for the performance differences among sorting techniques and perhaps some concrete evidence for the asymptotic behavior (how fast timing tends to infinity) of these techniques 1. Create a NetBeans Project named CompareSorts. It wil not have a constructor, but its main method will print out some performance information for a variety of sorting techniques. In particular, I want you to use Insertion, Selection, Merge, and Quick from algs4 and sort from java.util.Arrays. I will refer to the latter as the System sorting algorithm. 2. For the sake of these trials you should create random lists of Doubles in the range from 0 to 1, using method(s) from StdRandom. 3. Given a sorting algorithm, a list size, and a number of required trials, you should repeat . generate a random list of the given size, sort that list using the specified algorithm time this sorting using Stopwatch from algs4 update the running total. the required number of times. Compute the average time taken for this sorting algorithm on this size of list You should look at the function displayed on page 255 for some guideline for a part of this process 4. Given a sorting algorithm, an initial list size, an upper limit for the list size, and the number of trials per list-size, compute the average sorting time and the ratio of times as you steadily double the length of the lists (not exceeding the maximum size). The model for this is the program on page 192 5. Report your results from this previous step, for all the algorithms we are considering, in a table as shown in the first part of the Appendix. Use an initial list size of 1000 and double until the size exceeds 50,000. Ten trials per list-size l be fine 6. By now you should have determined that Selection Sort and Insertion Sort really are signif icantly slower than the other methods. Using only Merge, Quick, and System, repeat this exercise but allowing for lists up to but not exceeding 1,100,000. The second part of the Appendix gives an example of the kind of output I am looking for 7. One of the main things I want you to do as you design your solution is to modularize the computations as much as possible. Define class methods to accomplish individual parts of the process. None of these methods should, themselves, be very long and your main should call the method(s) it needs and not much else. For example, in my solution, none of the class methods is more than 11 lines long and main has fewer than 15 lines. Don't think of these as "goals" for your solution, but break things up into smal understandable pieces and then put these together. I don't want to see everything done in a monolithic main program!

this is the page no. 255 ..
can some one please help me with please. just give a way to do it assuming that we have add algs4.jar.
thank you!!

Answer 1

import java.lang.management.*;

public class Sort {

public static void main (String[] args) {

ThreadMXBean bean = ManagementFactory.getThreadMXBean(); // NOTE

int N = Integer.parseInt(args[0]);

System.out.println ("Generating " + N + " random numbers");
int[] a = new int[N];
for (int i=0; i<N; ++i) a[i] = (int)(Math.random()*(1<<30));

// To test a particular sorting algorithm, I make a copy of the original
// array, and then record the current "user time". After running the
// sort, I compute the elapsed time by taking the difference between the
// time and the time from before the sort.
if (false)
{
int[] c = new int[N];
for (int i=0; i<N; ++i) c[i] = a[i];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)

insertionSort(c);
System.out.printf ("Insertion sort took %f seconds.\n", // NOTE
(bean.getCurrentThreadUserTime()-t) / 1e9);
}

// Here is a section of code that you could use to start a mergesort.
// Merge Sort
{
int[] c = new int[N];
for (int i=0; i<N; ++i) c[i] = a[i];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)

mergeSort(c);
System.out.printf ("Mergesort took %f seconds.\n", // NOTE
(bean.getCurrentThreadUserTime()-t) / 1e9);
}

// Quick Sort - Feynman Liang 2-18-2012
{
int[] c = new int[N];
for (int i=0; i<N; ++i) c[i] = a[i];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)

quickSort(c);
System.out.printf ("Quicksort took %f seconds.\n", // NOTE
(bean.getCurrentThreadUserTime()-t) / 1e9);
}
// Extend testing times over <multiple> loops (set to false to
// disable)
if (false) {
int multiple = 100;
{
int[] c = new int[N];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)
for (int counter = 0; counter < multiple; counter++) {
for (int i=0; i<N; ++i) c[i] = a[i];
insertionSort(c);
}
System.out.printf ("Insertion sort * %d took %f seconds.\n",
(multiple),
(bean.getCurrentThreadUserTime()-t) / 1e9);
}
{
int[] c = new int[N];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)
for (int counter = 0; counter < multiple; counter++) {
for (int i=0; i<N; ++i) c[i] = a[i];
mergeSort(c);
}
System.out.printf ("Mergesort * %d took %f seconds.\n",
(multiple),
(bean.getCurrentThreadUserTime()-t) / 1e9);
}
{
int[] c = new int[N];

long t = bean.getCurrentThreadUserTime(); // NOTE (t is a *long*)
for (int counter = 0; counter < multiple; counter++) {
for (int i=0; i<N; ++i) c[i] = a[i];
quickSort(c);
}
System.out.printf ("Quicksort * %d took %f seconds.\n",
(multiple),
(bean.getCurrentThreadUserTime()-t) / 1e9);
}
}
}

/////////////////////////////////////////////////////////////////////////
// This method prints the contents of an array. You might use it during
// debugging.
/////////////////////////////////////////////////////////////////////////

public static void print(int[] a) {
for (int i=0; i<a.length; ++i)
System.out.println (a[i]);
System.out.println();
}

/////////////////////////////////////////////////////////////////////////
// This method compares the contents of two arrays. You might use it
// during debugging to compare the results of two different algorithms.
/////////////////////////////////////////////////////////////////////////

public static void check(int[] a, int[] b) {
for (int i=0; i<a.length; ++i)
if (a[i] != b[i])
throw new RuntimeException ("Error in sorting results");
}

/////////////////////////////////////////////////////////////////////////
// Here's the insertion sort.
/////////////////////////////////////////////////////////////////////////

public static void insertionSort(int[] a) {

int n = a.length;

for (int i=1; i<n; ++i) {

int t = a[i];
int j = i-1;
while (j >= 0 && t < a[j]) {
a[j+1] = a[j];
j--;
}
a[j+1] = t;
}
}

/////////////////////////////////////////////////////////////////////////
// MergeSort
/////////////////////////////////////////////////////////////////////////
public static int[] mergeSort(int[] a) {
// pre: array of integers
// post: sorted in non-desceasing order

int len = a.length;

int blocksize = 1;
while (blocksize < len) {
// invariant: a is in sorted blocks of size
// blocksize/2
int lo = 0;
while (lo < (len - blocksize)) {
// invariant: a[0..lo-1] is sorted in blocks of
// size blocksize
int hi = lo + 2 * blocksize - 1;
// check to see if we've run off a[]
if ((len - 1) < hi)
hi = len - 1;
inPlaceMerge(a,
blocksize,
lo,
hi);
lo = lo + 2*blocksize;
}
blocksize = blocksize * 2;
}
// returns merged sorted array (or single array)
return a;
}

public static void inPlaceMerge(int[] a, int blocksize, int lo, int hi) {
// pre: two sorted subarrays leftn and right
// post: a combined array sorted in non-decreasing order
int[] merged = new int[hi-lo+1];
int i = lo, j = lo + blocksize, k = 0;

while (i <= lo + blocksize - 1 && j <= hi) {
// invariant: merged[] contains all keys < a[i..lo +
// blocksize-1] and a[j..hi] sorted in non-decreasing
if (a[i] < a[j]) {
merged[k] = a[i];
i++;
}
else {
merged[k] = a[j];
j++;
}
k++;
}
// After i or j runs off its half, copy other remaining half
while(i <= lo + blocksize - 1) {
merged[k] = a[i];
i++;
k++;
}
while(j <= hi) {
merged[k] = a[j];
j++;
k++;
}

// Copy merged back in to a[lo..hi]
for (k = 0; k < merged.length; k++)
a[lo+k] = merged[k];
}

/////////////////////////////////////////////////////////////////////////
// quick Sort
/////////////////////////////////////////////////////////////////////////
public static int[] quickSort(int[] a) {
// pre: a = array of ints
// post: returns a sorted in non-decreasing order

// pass a to recursive qsort method
qsort(a, 0, a.length-1);
return a;
}

public static void qsort(int[] a, int lo, int hi) {
// pivot = median in small array, median of 3 in length > 7
int mid = (lo+hi)/2;
if ((hi - lo + 1) > 7) {
mid = medofthree(a, lo, mid, hi);
}
int pivot = a[mid];

int i = lo, j = hi;
while (i <= j) {
// Invariant: subarray [lo..i-1] contains keys < pivot
// and [j+1..hi] contains keys > pivot, [i-1..j+1]
// contains unpartitioned elements and pivots themselves
// so that i and j converge around the pivot

// set i to index of leftmost key > pivot
while (a[i] < pivot) i++;
// set j to rightmost index of key < pivot
while (a[j] > pivot) j--;
// if not overlapped, swap the two indexes
if (i <= j) {
swap(a, i++, j--);
}
}

// Recursively sort sub-partitions
if (lo < i-1) qsort(a, lo, i-1);
if (i < hi) qsort(a, i, hi);
}

public static void swap(int[] a, int i, int j) {
// swaps key at index i with key at index j in array a
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static int medofthree(int[] a, int lo, int mid, int hi) {
// finds the median of lo, mid, and hi
if (a[lo] < a[mid]) {
if (a[mid] < a[hi]) return mid;
else {
if (a[lo] < a[hi]) return hi;
else return lo;
}
}
else {
if (a[mid] > a[hi]) return mid;
else {
if (a[lo] > a[hi]) return hi;
else return lo;
}
}
}
}

//I have implemented for merge insertion and quick sort for other just add the rest of the sorting methods and n values and this code outputs a comparision of n different key with time multiplited by 100 like this,

N Insertion*100 Merge*100 Quick*100
500 & 0.01 & 0.09 & 0.07
1000 & 0.03 & 0.03 & 0.01
2500 & 0.12 & 0.05 & 0.04
5000 & 0.49 & 0.09 & 0.08
10000 & 1.99 & 0.19 & 0.12
25000 & 12.5 & 0.53 & 0.41