| Original | 3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 | 5 |
| after p=2 | 1 | 3 | 4 | 1 | 5 | 9 | 2 | 6 | 5 |
| after p=3 | 1 | 3 | 4 | 1 | 5 | 9 | 2 | 6 | 5 |
| after p=4 | 1 | 1 | 3 | 4 | 5 | 9 | 2 | 6 | 5 |
| after p=5 | 1 | 1 | 3 | 4 | 5 | 9 | 2 | 6 | 5 |
| after p=6 | 1 | 1 | 3 | 4 | 5 | 9 | 2 | 6 | 5 |
| after p=7 | 1 | 1 | 2 | 3 | 4 | 5 | 9 | 6 | 5 |
| after p=8 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 5 |
| after p=9 | 1 | 1 | 2 | 3 | 4 | 5 | 5 | 6 | 9 |
O(N) because the while loop terminates immediately. Of course, accidentally changing the test to include equalities raises the running time to quadratic for this type of input.
| Original | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| after 7-sort | 2 | 1 | 7 | 6 | 5 | 4 | 3 | 9 | 8 |
| after 3-sort | 2 | 1 | 4 | 3 | 5 | 7 | 6 | 9 | 8 |
| after 1-sort | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
The input is read in as
142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102
The result of the heapify is
879, 811, 572, 434, 543, 123, 142, 65, 111, 242, 453, 102
879 is removed from the heap and placed at the end. We'll place it in italics to signal that it is not part of the heap. 102 is placed in the hole and bubbled down, obtaining
811, 543, 572, 434, 453, 123, 142, 65, 111, 242, 102, 879
Continuing the process, we obtain
572, 543, 142, 434, 453, 123, 102, 65, 111, 242, 811, 879
543, 453, 142, 434, 242, 123, 102, 65, 111, 572, 811, 879
453, 434, 142, 111, 242, 123, 102, 65, 543, 572, 811, 879
434, 242, 142, 111, 65, 123, 102, 453, 543, 572, 811, 879
242, 111, 142, 102, 65, 123, 434, 453, 543, 572, 811, 879
142, 111, 123, 102, 65, 242, 434, 453, 543, 572, 811, 879
123, 111, 65, 102, 142, 242, 434, 453, 543, 572, 811, 879
111, 102, 65, 123, 142, 242, 434, 453, 543, 572, 811, 879
102, 65, 111, 123, 142, 242, 434, 453, 543, 572, 811, 879
65, 102, 111, 123, 142, 242, 434, 453, 543, 572, 811, 879
First the sequence {3, 1, 4, 1} is sorted. To do this, the sequence {3, 1} is sorted. This involves sorting {3} and {1}, which are base cases, and merging the result to obtain {1, 3}. The sequence {4, 1} is likewise sorted into {1, 4}. Then these two sequences are merged to obtain {1, 1, 3, 4}. The second half is sorted similarly, eventually obtaining {2, 5, 6, 9}. The merged result is then easily computed as {1, 1, 2, 3, 4, 5, 6, 9}.
The original input is
3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5
After sorting the first, middle, and last elements, we have
3, 1, 4, 1, 5, 5, 2, 6, 5, 3, 9
Thus the pivot is 5. Hiding it gives
3, 1, 4, 1, 5, 3, 2, 6, 5, 5, 9
The first swap is between two fives. Then next swap has i and j crossing. Thus the pivot is swapped back with i:
3, 1, 4, 1, 5, 3, 2, 5, 5, 6, 9
We now recursively quicksort the first eight elements:
3, 1, 4, 1, 5, 3, 2, 5
Sorting the three appropriate elements gives
1, 1, 4, 3, 5, 3, 2, 5
Thus the pivot is 3, which gets hidden:
1, 1, 4, 2, 5, 3, 3, 5
The first swap is between 4 and 3:
1, 1, 3, 2, 5, 4, 3, 5
The next swap crosses pointers, so is undone; i points to 5, and so the pivot is swapped:
1, 1, 3, 2, 3, 4, 5, 5
A recursive call is now made to sort the first four elements. The pivot is 1, and the partition does not make any changes. The recursive calls are made, but the subfiles are below the cutoff, so nothing is done. Likewise, the last three elements constitute a base case, so nothing is done. We return to the original call, which now calls quicksort recursively on the right-hand side, but again, there are only three elements, so nothing is done. The result is
1, 1, 3, 2, 3, 4, 5, 5, 5, 6, 9
which is cleaned up by insertion sort.
We add a dummy N + 1th element, which we'll call maybe. maybe satisfies false < maybe < true. Partition the array around maybe, using the standard quicksort techniques. Then swap maybe and the N + 1th element. The first N elements are then correctly arranged.
When the pivot key is always the smallest (or largest) key in the subarray being partitioned, the partition sizes are as lopsided as possible, causing QuickSort to run in time O( n^2 ). For example, if the pivot key is chosen as the middle key in A[i:j] with pivot = A[(i+j)/2], an initial unsorted array such as A = [2, 7, 4, 1, 3, 5, 6] will cause the QuickSort algorithm to run in worst case time. The sequence of right partitions, in this case, is:
array index i = 0 1 2 3 4 5 6 initial array A = [ 2, 7, 4, 1, 3, 5, 6 ], swap A[0] == 2 & A[3] == 1 R = A[1:6] in A = [ 1, 7, 4, 2, 3, 5, 6 ], swap A[1] == 7 & A[3] == 2 R = A[2:6] in A = [ 1, 2, 4, 7, 3, 5, 6 ], swap A[2] == 4 & A[4] == 3 R = A[3:6] in A = [ 1, 2, 3, 7, 4, 5, 6 ], swap A[3] == 7 & A[4] == 4 R = A[4:6] in A = [ 1, 2, 3, 4, 7, 5, 6 ], swap A[4] == 7 & A[5] == 5 R = A[5:6] in A = [ 1, 2, 3, 4, 5, 7, 6 ], swap A[5] == 7 & A[6] == 6 R = A[6:6] in A = [ 1, 2, 3, 4, 5, 6, 7 ].
In InsertionSort, for each i in 1:n-1 half the keys in A[0:i-1] are moved (i.e., i/2 of the i keys in A[0:i-1] are moved), on the average, after which A[0:i-1] is moved into the hole opened up for insertion. Summing up the total number of these moves gives the sum S, where
S = SumOf{i=1 to n-1} (i/2 + 1) = (1/2 * (SumOfPi=1 to n-1} i ) + (n-1)
= 1/2 * ( (n * (n-1)) / 2) + (n-1)
= 1/4 * [ n * (n-1) + 4(n-1)]
S = ( (n+4)(n-1) )/4 moves of keys.
In SelectionSort, one pair of keys is exchanged for each i in the range
1:n-1, meaning that exactly (n-1) pairwise exchanges of keys take
place. If each pairwise exchange takes 3 moves, the total number
of key moves is 3n-3 in SelectionSort. Because 3n-3 is less than
(n+4)( n-1)/4 for all n >=9, SelectionSort moves fewer keys than
InsertionSort on the average whenever the array to be sorted
contains nine or fewer keys.
[On the other hand, InsertionSort performs half as many key
comparisons on the average as SelectionSort, with InsertionSort
performing n(n-1)/4 comparisons, and SelectionSort performing n(n-1)/2
comparisons.]
The following solution was provided by Carl Huttenlocher
File ReadMe.txt:
Name: Carl Huttenlocher Problem Set 4. Submitted files: 1) sort.java To compile: javac sort.java TO run: java sort > outputname.out 2) sortresult.out 3) sortresult2.out. 4) Analysis.txt 5) ReadMe.txt 6) graph output files. 3 of them titled: reversegraph.pbm, sortedgraph.pbm and randomgraph.pbm Description of files 1) sort.java This program has three classes: 1) QueueNode. This class stores the integers that is used in the linked list queue implementation used in the radix sort. 2) QueueList. The actual queue used in radix sort. The Linked List implementation allows for enqueues and dequeues of the integers. It also has an isEmpty method. 3) sort. This is the main class. It has 5 different sorting methods. The mergeSort, heapSort and quickSort are all from Weiss. The quickSort uses the median of 3 pivot method which affects the analysis (see analysis file). The radixSort uses two length 10 arrays of queues and for each of the ten passes it alternates between these arrays. Other Notes: Random Numbers: As Can suggested I minimized the random number draws. So, only one array of 10,000 random numbers is created. A subset of the array is then copied for the N=1000, 100 and 10 cases. For radix sort since we need positive numbers I take the absolute value of those 10,000 numers when we are in the radix sort part of the loop. So, the same numbers are used but the absolute value is taken. The sorted and reverse sorted numbers are the same random numbers but sorted and reverse ordered. I use quicksort to sort the array for the sorted part. I then reverse the sorted list in a for loop for the reverse sorted random numbers. Files created. The program automatically creates 3 graphs (as as 5 data output files, not 15 as I overwrite the output files. All 15 can be seen in the overall output file). The graphs are reversegraph.pbm, sortedgraph.pbm and randomgraph.pbm. The printed graphs I have supplied were both done in postscript since this was something I had the software to view. The graphs have time on y-axis and N on x-axis as Can suggested and the recitation notes had. I also included a printout for Log N instead (log of base 10 so it has 1, 2, 3, 4 on x-axis). Notes about output: 1) sortresult.out This is the output file that the program currently produces. It just outputs the running times for each of the scenarios. This output includes a summary printout of each of the sorting methods for the 3 number types for the various sizes of N and the time is in seconds. The printout is just the datafiles that are used to plot the graph's. A little header is printed before each one.Note that this file has much shorter running times than the next output file. The only difference was that this was run on fozimane while the next run was on cunix! 2) sortresult2.out Besides being run on cunix this output file also adds a section which prints out the pre-sorted and post numbers for each of the 3 cases (random, sorted and reverse) for N=10 as a check.
File Analysis.txt:
Analysis of Sorts: Major Points: 1) First of all quicksort is the fastest for all implementations. The reason it doesn't have a worst case O(N^2) performance in the case of the sorted or reverse sorted list is because we use the median of 3 method to pick the pivot so we never get into the situation with the sorted list that we keep partitioning off 1 and N-1. 2) Radix Sort has roughly O(N) growth but because of the assignments with the two arrays of queues it takes more memory and seems to have some large overhead in the small N cases so that it lags behind the performance of MergeSort and HeapSort for the sizes of N we have chosen. However, note that for the random number case from N=100, N=1000, N=10,000 radix sort goes from 0.015 sec to 0.155 seconds to 1.81 sec or close to linear growth. Meanwhile HeapSort (which is very similar to Mergesort although MergeSort is slightly faster) starts out the same sequence at 0.002 seconds then 0.047 sec and finally 0.621 sec. So, it starts out (at N=100) that radixsort takes 8 times as long but it is only 3 times as long at n=10,000. So, my guess is that at N=1 million or so radixsort would be faster. 3) Both Heapsort and Mergesort seem to be growing at roughly O(NlogN) as they are definitely growing faster than linearly. 4) Quicksort also seems to be growing slightly faster than linearly. 5) SelectionSort is the slowest for all lists. It is clearly O(n^2) as it goes from N=100, N=1000, N=10,000 for random from 0.006 sec to 0.589 to 59.928 which is clearly O(N^2) growth. Also it's interesting to note that whether the list is reverse ordered or not does not influence the sort times by much.File sort.java:
import java.io.*;
import java.util.*;
import java.lang.System.*;
//package sort;
class QueueNode
{
QueueNode(int numb)
{
this(numb, null);
}
public int num; // the number to be sorted
public QueueNode next; // Link to next Node.
public QueueNode(int numb, QueueNode n) // constructor
{
num = numb; // initialize data
next=n;
}
}
class QueueList
{
public QueueList () //constructor
{
first=null;
last=null;
}
private QueueNode first;
private QueueNode last;
public boolean isEmpty()
{
return first==null;
}
public void enqueue(int d)
{
QueueNode newNode= new QueueNode(d);
if (isEmpty() )
first=newNode;
else
last.next=newNode;
last=newNode;
}
public int dequeue ()
{
int temp=first.num;
if (first.next==null) //only one item
last=null;
first=first.next;
return temp;
}
}
public class sort {
public static void selectionSort( int [ ] a)
{
int j, k, min;
for(j=0; j<a.length-1;j++)
{
min=j;
for(k=j+1; k<a.length; k++)
{
if(a[k]<a[min])
min=k;
}
swapReferences(a, j, min);
}
}
/**
* Standard heapsort.
* @param a an array of Comparable items.
*/
public static void heapSort( int [ ] a )
{
/* 1*/ for( int i = a.length / 2; i >= 0; i-- ) /* buildHeap */
/* 2*/ percDown( a, i, a.length );
/* 3*/ for( int i = a.length - 1; i > 0; i-- )
{
/* 4*/ swapReferences( a, 0, i ); /* deleteMax */
/* 5*/ percDown( a, 0, i );
}
}
/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private static int leftChild( int i )
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @index i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private static void percDown( int [ ] a, int i, int n )
{
int child;
int tmp;
/* 1*/ for( tmp = a[ i ]; leftChild( i ) < n; i = child )
{
/* 2*/ child = leftChild( i );
/* 3*/ if( child != n - 1 && a[ child ]<a[ child + 1 ] )
/* 4*/ child++;
/* 5*/ if( tmp < a[ child ] )
/* 6*/ a[ i ] = a[ child ];
else
/* 7*/ break;
}
/* 8*/ a[ i ] = tmp;
}
/**
* Mergesort algorithm.
* @param a an array of Comparable items.
*/
public static void mergeSort( int [ ] a )
{
int [ ] tmpArray = new int[ a.length ];
mergeSort2( a, tmpArray, 0, a.length - 1 );
}
/**
* Internal method that makes recursive calls.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void mergeSort2( int [ ] a, int [ ] tmpArray,
int left, int right )
{
if( left < right )
{
int center = ( left + right ) / 2;
mergeSort2( a, tmpArray, left, center );
mergeSort2( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}
/**
* Internal method that merges two sorted halves of a subarray.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
private static void merge( int [ ] a, int [ ] tmpArray,
int leftPos, int rightPos, int rightEnd )
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ]<= a[ rightPos ] )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
/**
* Quicksort algorithm.
* @param a an array of Comparable items.
*/
public static void quickSort( int [ ] a )
{
quicksort2( a, 0, a.length - 1 );
}
private static final int CUTOFF = 3;
/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static final void swapReferences( int [ ] a, int index1, int index2 )
{
int tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
private static int median3( int [ ] a, int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ]< a[ left ] )
swapReferences( a, left, center );
if( a[ right ] < a[ left ] )
swapReferences( a, left, right );
if( a[ right ] < a[ center ] )
swapReferences( a, center, right );
// Place pivot at position right - 1
swapReferences( a, center, right - 1 );
return a[ right - 1 ];
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void quicksort2( int [ ] a, int left, int right )
{
/* 1*/ if( left + CUTOFF <= right )
{
/* 2*/ int pivot = median3( a, left, right );
// Begin partitioning
/* 3*/ int i = left, j = right - 1;
/* 4*/ for( ; ; )
{
/* 5*/ while( a[ ++i ] < pivot ) { }
/* 6*/ while( a[ --j ] > pivot ) { }
/* 7*/ if( i < j )
/* 8*/ swapReferences( a, i, j );
else
/* 9*/ break;
}
/*10*/ swapReferences( a, i, right - 1 ); // Restore pivot
/*11*/ quicksort2( a, left, i - 1 ); // Sort small elements
/*12*/ quicksort2( a, i + 1, right ); // Sort large elements
}
else // Do an insertion sort on the subarray
/*13*/ insertionSort( a, left, right );
}
/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void insertionSort( int [ ] a, int left, int right )
{
for( int p = left + 1; p <= right; p++ )
{
int tmp = a[ p ];
int j;
for( j = p; j > left && tmp < a[ j - 1 ]; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}
public static void radixsort (int [ ] a)
{
QueueList [ ] source1 = new QueueList [10];
QueueList [ ] source2 = new QueueList [10];
boolean src2=true; //boolean which tracks if source2 is destination
int tmp;
int digit=0; //the digit in the integers we are sorting
for (int k=0; k<10; k++)
{ //initialize 2 arrays of queue's
source1[k] = new QueueList();
source2[k] = new QueueList();
}
for (int j=0; j<a.length; j++)
{
source1[getDigit(a[j],digit)].enqueue(a[j]);
}
for (digit=1; digit<10; digit++)
{
if (src2) //go from source1 to source2
{
for (int k=0; k<10; k++)
{
while (!source1[k].isEmpty() )
{
tmp=source1[k].dequeue();
source2[getDigit(tmp,digit)].enqueue(tmp);
}
source1[k] = new QueueList(); //reinitialize
}
src2=false; //switch direction
}
else //go from source2 to source1
{
for (int k=0; k<10; k++)
{
while (!source2[k].isEmpty() )
{
tmp=source2[k].dequeue();
source1[getDigit(tmp,digit)].enqueue(tmp);
}
source2[k] = new QueueList(); //reinitialize
}
src2=true; //switch direction
} //end else
} //end for loop
int j=0;
if (src2)
{
for (int k=0; k<10; k++)
{
while (!source1[k].isEmpty() )
{
a[j]=source1[k].dequeue();
j++;
}
}
}
else
{
for (int k=0; k<10; k++)
{
while (!source2[k].isEmpty() )
{
a[j]=source2[k].dequeue();
j++;
}
}
}
}
//return the digit in position d
public static int getDigit (int key, int d)
{
return ( (key/(int)Math.pow(10,d) )%10);
}
public static void main( String [ ] args )
{
//Create a reverse ordered array
int numitems;
int numtype; //1=random, 2=sorted, 3=reverse
int sorttype; //1=selection, 2=merge, 3=heap, 4=quick, 5=radix
int [ ] list = new int[10];
int maxitems=10000;
int [ ] originalarray =new int[maxitems];
int [ ] temparr = new int[10];
FileWriter fw1=null, fw2=null, fw3=null, fw4=null, fw5=null, fw6=null;
PrintWriter pw1=null, pw2=null, pw3=null, pw4=null, pw5=null, pw6=null;
int [ ] temparray = new int[10];
String outputfile="";
int m=0;
Random rm = new Random();
//make only 1 random number array of 10,000 for use in program
for(int n = 0 ; n <maxitems; n++)
{
originalarray[n] = rm.nextInt();
}
for (numtype=1; numtype<4; numtype++)
{
try
{
fw1= new FileWriter("selectionsort.dat");
fw2= new FileWriter("mergesort.dat");
fw3= new FileWriter("heapsort.dat");
fw4= new FileWriter("quicksort.dat");
fw5= new FileWriter("radixsort.dat");
pw1 =new PrintWriter(fw1);
pw2 =new PrintWriter(fw2);
pw3 =new PrintWriter(fw3);
pw4 =new PrintWriter(fw4);
pw5 =new PrintWriter(fw5);
}
catch (IOException ioe) {System.out.println(ioe);}
//double num;
//int numitem;
for (numitems=10; numitems<=maxitems; numitems=numitems*10)
{
//num=java.lang.Math.log((double)numitems)/(java.lang.Math.log((double)10));
//numitem=(int)num;
temparray= new int[numitems];
list=new int[numitems];
//copy n random integers store in an array
if (numtype==1)
{
System.arraycopy(originalarray,0,temparray,0,numitems);
}
//make it a sorted list instead
if (numtype==2)
{
System.arraycopy(originalarray,0,temparray,0,numitems);
sort.quickSort(temparray); //sort the array of random integers
}
//make it a reverse ordered list
if (numtype==3)
{
m=0;
System.arraycopy(originalarray,0,temparray,0,numitems);
sort.quickSort(temparray);
System.arraycopy(temparray,0,list,0,numitems);
for(int n=numitems-1; n>=0; n--)
{
temparray[m]=list[n];
m++;
}
} //if numtype==3
for(sorttype=1; sorttype<6; sorttype++)
{
System.arraycopy(temparray,0,list,0,numitems);
if (sorttype==5)
{
for(int n=0; n<numitems;n++)
{
list[n]=Math.abs(list[n]);
}
if (numtype==2)
sort.quickSort(list);
else if (numtype==3)
{
temparr= new int[numitems];
sort.quickSort(list);
System.arraycopy(list,0,temparr,0,numitems);
m=0;
for(int n=numitems-1; n>=0; n--)
{
list[m]=temparr[n];
m++;
}
}
}
//for displaying n=10 case
/*
if (numitems==10)
{
System.out.println("Numbers before Sorting:");
for (int n=0; n<numitems; n++)
System.out.print(list[n]+" ");
System.out.println(" ");
}*/
long starttime, endtime;
double totalseconds;
starttime=System.currentTimeMillis();
//sort for each type of sort
if(sorttype==1)
{
sort.selectionSort(list);
// System.out.print("Doing Selection Sort for "+numitems+" of type "
// +numtype);
if(numitems==10)
System.out.println("Numbers after Selection Sort");
endtime=System.currentTimeMillis();
totalseconds = (double)((endtime-starttime)/(double) 1000);
// System.out.println(" Sort took "+totalseconds+" seconds.");
pw1.print(numitems+"\t"+totalseconds+"\n");
}
else if (sorttype==2)
{
sort.mergeSort(list);
// System.out.print("Doing Merge Sort for "+numitems+" of type "
// +numtype);
if(numitems==10)
System.out.println("Numbers after Merge Sort");
endtime=System.currentTimeMillis();
totalseconds = (double)((endtime-starttime)/(double) 1000);
// System.out.println(" Sort took "+totalseconds+" seconds.");
pw2.print(numitems+"\t"+totalseconds+"\n");
}
else if (sorttype==3)
{
sort.heapSort(list);
// System.out.print("Doing Heap Sort for "+numitems+" of type "
// +numtype);
if(numitems==10)
System.out.println("Numbers after Heap Sort");
endtime=System.currentTimeMillis();
totalseconds = (double)((endtime-starttime)/(double) 1000);
// System.out.println(" Sort took "+totalseconds+" seconds.");
pw3.print(numitems+"\t"+totalseconds+"\n");
}
else if (sorttype==4)
{
sort.quickSort(list);
// System.out.print("Doing Quick Sort for "+numitems+" of type "
// +numtype);
if(numitems==10)
System.out.println("Numbers after Quick Sort");
endtime=System.currentTimeMillis();
totalseconds = (double)((endtime-starttime)/(double) 1000);
// System.out.println(" Sort took "+totalseconds+" seconds.");
pw4.print(numitems+"\t"+totalseconds+"\n");
}
else if (sorttype==5)
{
sort.radixsort(list);
// System.out.print("Doing Radix Sort for "+numitems+" of type "
// +numtype);
if(numitems==10)
System.out.println("Numbers after Radix Sort");
endtime=System.currentTimeMillis();
totalseconds = (double)((endtime-starttime)/(double) 1000);
// System.out.println(" Sort took "+totalseconds+" seconds.");
pw5.print(numitems+"\t"+totalseconds+"\n");
}
//for displaying n=10 case
/*
if(numitems==10)
{for (int n=0; n<numitems; n++)
System.out.print(list[n]+" ");
System.out.println(" ");} */
} //end for sorttype
} // end for numitems
pw1.close();
pw2.close();
pw3.close();
pw4.close();
pw5.close();
//print the files created so as to get a nice printout of results
if (numtype==1)
System.out.println("Results for Random Numbers:");
else if(numtype==2)
System.out.println("Results for Sorted Numbers:");
else if(numtype==3)
System.out.println("Results for Reverse Sorted Numbers:");
int i=0;
FileReader fr;
try
{
fr=new FileReader("selectionsort.dat");
System.out.println("Selection Sort:");
while (i!=-1)
{
i=fr.read();
if(i!=-1)
System.out.print((char)i);
}
} //end try
catch (IOException ioe) {System.out.println(ioe);}
i=0;
try
{
fr=new FileReader("mergesort.dat");
System.out.println("Merge Sort:");
while (i!=-1)
{
i=fr.read();
if(i!=-1)
System.out.print((char)i);
}
}
catch (IOException ioe) {System.out.println(ioe);}
i=0;
try
{
fr=new FileReader("heapsort.dat");
System.out.println("Heap Sort:");
while (i!=-1)
{
i=fr.read();
if(i!=-1)
System.out.print((char)i);
}
}
catch (IOException ioe) {System.out.println(ioe);}
i=0;
try
{
fr=new FileReader("quicksort.dat");
System.out.println("Quick Sort:");
while (i!=-1)
{
i=fr.read();
if(i!=-1)
System.out.print((char)i);
}
}
catch (IOException ioe) {System.out.println(ioe);}
i=0;
try
{
fr=new FileReader("radixsort.dat");
System.out.println("Radix Sort:");
while (i!=-1)
{
i=fr.read();
if(i!=-1)
System.out.print((char)i);
}
} //end try
catch (IOException ioe) {System.out.println(ioe);}
//create GNU plot file
try
{
fw6= new FileWriter("5-plots.gp");
pw6 =new PrintWriter(fw6);
// pw6.print("set terminal postscript\n");
pw6.print("set terminal pbm monochrome small\n");
// pw6.print("set terminal dumb 79 35\n");
if(numtype==1)
{
pw6.print("set output \"randomgraph.pbm\"\n");
//pw6.print("set output \"randomgraph.bmp\"\n");
pw6.print("set title \"Random Numbers Plot\"\n");
}
else if(numtype==2)
{
pw6.print("set output \"sortedgraph.pbm\"\n");
//pw6.print("set output \"sortedgraph.bmp\"\n");
pw6.print("set title \"Sorted Numbers Plot\"\n");
}
else if(numtype==3)
{
pw6.print("set output \"reversegraph.pbm\"\n");
//pw6.print("set output \"reversegraph.bmp\"\n");
pw6.print("set title \"Reverse Sorted Numbers Plot\"\n");
}
pw6.print("set xlabel \"Input size\"\n");
pw6.print("set ylabel \"Time (sec)\"\n");
pw6.print("set data style linespoints\n");
pw6.print("plot \"selectionsort.dat\" title \"SelectionSort\", \\\n");
pw6.print("\"mergesort.dat\" title \"MergeSort\", \\\n");
pw6.print("\"heapsort.dat\" title \"HeapSort\", \\\n");
pw6.print("\"quicksort.dat\" title \"QuickSort\", \\\n");
pw6.print("\"heapsort.dat\" title \"RadixSort\"\n");
pw6.close();
} //end try
catch (IOException ioe) {System.out.println(ioe);}
//run GNU plot
try {
Runtime rt = Runtime.getRuntime(); // step 1
Process prcs = rt.exec("/c/u/2/c/cs3139-2/bin/gnuplot 5-plots.gp"); // step 2
InputStreamReader isr = // step 3
new InputStreamReader( prcs.getInputStream() );
BufferedReader br = new BufferedReader( isr ); // step 4
String line;
while ((line = br.readLine()) != null)
System.out.println(line);
}
catch (IOException ioe) { System.out.println(ioe); }
} //end for numtype
} //end main
} //end class sort
File sortresult.out:
Numbers after Selection Sort Numbers after Merge Sort Numbers after Heap Sort Numbers after Quick Sort Numbers after Radix Sort Results for Random Numbers: Selection Sort: 10 0.0020 100 0.0060 1000 0.589 10000 59.928 Merge Sort: 10 0.0 100 0.0020 1000 0.031 10000 0.482 Heap Sort: 10 0.0 100 0.0020 1000 0.047 10000 0.621 Quick Sort: 10 0.0010 100 0.0010 1000 0.014 10000 0.167 Radix Sort: 10 0.0070 100 0.015 1000 0.155 10000 1.81 Numbers after Selection Sort Numbers after Merge Sort Numbers after Heap Sort Numbers after Quick Sort Numbers after Radix Sort Results for Sorted Numbers: Selection Sort: 10 0.0010 100 0.0060 1000 0.742 10000 62.91 Merge Sort: 10 0.0010 100 0.0020 1000 0.027 10000 0.389 Heap Sort: 10 0.0010 100 0.0030 1000 0.048 10000 0.683 Quick Sort: 10 0.0010 100 0.0 1000 0.0070 10000 0.103 Radix Sort: 10 0.0030 100 0.014 1000 0.166 10000 1.731 Numbers after Selection Sort Numbers after Merge Sort Numbers after Heap Sort Numbers after Quick Sort Numbers after Radix Sort Results for Reverse Sorted Numbers: Selection Sort: 10 0.0010 100 0.0060 1000 0.656 10000 66.283 Merge Sort: 10 0.0010 100 0.0020 1000 0.027 10000 0.365 Heap Sort: 10 0.0 100 0.0030 1000 0.039 10000 0.619 Quick Sort: 10 0.0010 100 0.0010 1000 0.012 10000 0.165 Radix Sort: 10 0.0030 100 0.015 1000 0.143 10000 2.073
File sortresult2.out
Numbers before Sorting: 171929467 -942061380 -468560141 -2026880628 -910229295 1151025635 890045525 -682932256 2118214438 -2044169362 Numbers after Selection Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 171929467 -942061380 -468560141 -2026880628 -910229295 1151025635 890045525 -682932256 2118214438 -2044169362 Numbers after Merge Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 171929467 -942061380 -468560141 -2026880628 -910229295 1151025635 890045525 -682932256 2118214438 -2044169362 Numbers after Heap Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 171929467 -942061380 -468560141 -2026880628 -910229295 1151025635 890045525 -682932256 2118214438 -2044169362 Numbers after Quick Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 171929467 942061380 468560141 2026880628 910229295 1151025635 890045525 682932256 2118214438 2044169362 Numbers after Radix Sort 171929467 468560141 682932256 890045525 910229295 942061380 1151025635 2026880628 2044169362 2118214438 Results for Random Numbers: Selection Sort: 10 0.0 100 0.011 1000 2.591 10000 135.141 Merge Sort: 10 0.017 100 0.0050 1000 0.128 10000 0.942 Heap Sort: 10 0.0020 100 0.015 1000 0.109 10000 0.849 Quick Sort: 10 0.0010 100 0.01 1000 0.026 10000 0.234 Radix Sort: 10 0.061 100 0.029 1000 0.231 10000 3.695 Numbers before Sorting: -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers after Selection Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers after Merge Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers after Heap Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers after Quick Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 171929467 468560141 682932256 890045525 910229295 942061380 1151025635 2026880628 2044169362 2118214438 Numbers after Radix Sort 171929467 468560141 682932256 890045525 910229295 942061380 1151025635 2026880628 2044169362 2118214438 Results for Sorted Numbers: Selection Sort: 10 0.0 100 0.0050 1000 2.723 10000 123.819 Merge Sort: 10 0.0010 100 0.0020 1000 0.11 10000 0.421 Heap Sort: 10 0.0 100 0.0020 1000 0.246 10000 0.703 Quick Sort: 10 0.0010 100 0.0 1000 0.0090 10000 0.107 Radix Sort: 10 0.0020 100 0.04 1000 0.676 10000 2.073 Numbers before Sorting: 2118214438 1151025635 890045525 171929467 -468560141 -682932256 -910229295 -942061380 -2026880628 -2044169362 Numbers after Selection Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 2118214438 1151025635 890045525 171929467 -468560141 -682932256 -910229295 -942061380 -2026880628 -2044169362 Numbers after Merge Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 2118214438 1151025635 890045525 171929467 -468560141 -682932256 -910229295 -942061380 -2026880628 -2044169362 Numbers after Heap Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 2118214438 1151025635 890045525 171929467 -468560141 -682932256 -910229295 -942061380 -2026880628 -2044169362 Numbers after Quick Sort -2044169362 -2026880628 -942061380 -910229295 -682932256 -468560141 171929467 890045525 1151025635 2118214438 Numbers before Sorting: 2118214438 2044169362 2026880628 1151025635 942061380 910229295 890045525 682932256 468560141 171929467 Numbers after Radix Sort 171929467 468560141 682932256 890045525 910229295 942061380 1151025635 2026880628 2044169362 2118214438 Results for Reverse Sorted Numbers: Selection Sort: 10 0.0060 100 0.0070 1000 1.167 10000 99.297 Merge Sort: 10 0.0010 100 0.0020 1000 0.039 10000 0.71 Heap Sort: 10 0.0010 100 0.0030 1000 0.108 10000 0.914 Quick Sort: 10 0.0010 100 0.019 1000 0.024 10000 0.207 Radix Sort: 10 0.0030 100 0.021 1000 0.352 10000 2.236