Program Description:
This program sorts an array of various sizes that has random numbers
with duplicates in it. This program uses two sorting methods to
sort each of the arrays the merge sort and the shell sort method.
This program also calculates the time taken to sort each of the
arrays and prints it in the tabular form. There are five arrays that
are sorted in this program, each of sizes 100, 10^3, 10^4, 10^5, and 10^6
all the arrays store random numbers in it which range from n to n/2,
where n is the size of the array.
/**
* @(#)Assign02.java
*
* Assign02 application
*
* @author Ramanpreet Singh
* @version 1.00 2011/3/9
*/
import java.util.Random;
import java.util.Timer;
import java.util.Arrays;
public class Assign02
{
public static void main(String[] args)
{
final int SIZE1 = 100; //constant SIZE1 for the first array
final int SIZE3 = 1000; //constant SIZE1 for the second array
final int SIZE4 = 10000; //constant SIZE1 for the third array
final int SIZE5 = 100000; //constant SIZE1 for the fourth array
final int SIZE6 = 1000000; //constant SIZE1 for the fifth array
int i; //used as a counter in the for loop
Random gen = new Random(); //The random generator to generate
//and store random numbers in the arrays
int[] n1 = new int[SIZE1]; //first array to be sorted with size = 100
//with numbers ranging from 1-50
int[] n3 = new int[SIZE3]; //first array to be sorted with size = 1000
//with numbers ranging from 1-500
int[] n4 = new int[SIZE4]; //first array to be sorted with size = 10000
//with numbers ranging from 1-5000
int[] n5 = new int[SIZE5]; //first array to be sorted with size = 100000
//with numbers ranging from 1-50000
int[] n6 = new int[SIZE6]; //first array to be sorted with size = 1000000
//with numbers ranging from 1-500000
System.out.println("-- ===================================================== --");
System.out.println("-- The Unsorted array of 100 items with some duplicates: --");
System.out.println("-- ===================================================== --");
//for loop that stores random numbers in the array
//with SIZE1 100 and it aslo stores some duplicates
for(i = 0; i < SIZE1; i++)
{
n1[i] = gen.nextInt(SIZE1/2)+1;
if((i+1)%10 == 0)
{
System.out.println(n1[i]);
}
else
{
System.out.print(n1[i] + ",\t");
}
}
int[] nMergeSort = Arrays.copyOf(mergeSort(n1), SIZE1);
System.out.println("-- ======================================================================== --");
System.out.println("-- The Sorted array of 100 items with some duplicates using the MERGE SORT: --");
System.out.println("-- ======================================================================== --");
for(i = 0; i < SIZE1; i++)
{
if((i+1)%10 == 0)
{
System.out.println(nMergeSort[i]);
}
else
{
System.out.print(nMergeSort[i] + ",\t");
}
}
int[] nShellSort = Arrays.copyOf(shellSort(n1), SIZE1);
System.out.println("-- ======================================================================== --");
System.out.println("-- The Sorted array of 100 items with some duplicates using the SHELL SORT: --");
System.out.println("-- ======================================================================== --");
for(i = 0; i < SIZE1; i++)
{
if((i+1)%10 == 0)
{
System.out.println(nMergeSort[i]);
}
else
{
System.out.print(nMergeSort[i] + ",\t");
}
}
//------------------------------------- Tabular Printing after this part -------------------//
// When N = 1000
for(i = 0; i < SIZE3; i++)
{
n3[i] = gen.nextInt(SIZE3/2)+1;
}
//Merge Sort
long tStart = System.currentTimeMillis(); //stores the current system time in milliseconds
//even before the merge sort starts
nMergeSort = Arrays.copyOf(mergeSort(n3), SIZE3);
long tEnd = System.currentTimeMillis(); //stores the current system time in milliseconds
//after the merge sort is over
long t3MS = tEnd - tStart; //time taken for MERGE sort when n = 1000
//Shell Sort
tStart = System.currentTimeMillis();
nShellSort = Arrays.copyOf(shellSort(n3), SIZE3);
tEnd = System.currentTimeMillis();
long t3SS = tEnd - tStart; //time taken for SHELL sort when n = 1000
//-----------------------------------------------------------------------------------------------
// When N = 10000
for(i = 0; i < SIZE4; i++)
{
n4[i] = gen.nextInt(SIZE4/2)+1;
}
//Merge Sort
tStart = System.currentTimeMillis();
nMergeSort = Arrays.copyOf(mergeSort(n4), SIZE3);
tEnd = System.currentTimeMillis();
long t4MS = tEnd - tStart; //time taken for MERGE sort when n = 10000
//Shell Sort
tStart = System.currentTimeMillis();
nShellSort = Arrays.copyOf(shellSort(n4), SIZE3);
tEnd = System.currentTimeMillis();
long t4SS = tEnd - tStart; //time taken for SHELL sort when n = 10000
//-----------------------------------------------------------------------------------------------
// When N = 100000
for(i = 0; i < SIZE5; i++)
{
n5[i] = gen.nextInt(SIZE5/2)+1;
}
//Merge Sort
tStart = System.currentTimeMillis();
nMergeSort = Arrays.copyOf(mergeSort(n5), SIZE3);
tEnd = System.currentTimeMillis();
long t5MS = tEnd - tStart; //time taken for MERGE sort when n = 100000
//Shell Sort
tStart = System.currentTimeMillis();
nShellSort = Arrays.copyOf(shellSort(n5), SIZE3);
tEnd = System.currentTimeMillis();
long t5SS = tEnd - tStart; //time taken for SHELL sort when n = 100000
//-----------------------------------------------------------------------------------------------
// When N = 1000000
for(i = 0; i < SIZE6; i++)
{
n6[i] = gen.nextInt(SIZE6/2)+1;
}
tStart = System.currentTimeMillis();
nMergeSort = Arrays.copyOf(mergeSort(n6), SIZE3);
tEnd = System.currentTimeMillis();
long t6MS = tEnd - tStart; //time taken for MERGE sort when n = 1000000
//Shell Sort
tStart = System.currentTimeMillis();
nShellSort = Arrays.copyOf(shellSort(n6), SIZE3);
tEnd = System.currentTimeMillis();
long t6SS = tEnd - tStart; //time taken for SHELL sort when n = 1000000
//-----------------------------------------------------------------------------------------------
//TABULAR PRINTOUT -----------------------------------------------------------------------------
System.out.println("\n\n--- ================================================================= ---");
System.out.println("|\tSorting Method\t\tValue(n)\t\t\tTime taken(milli-seconds)\t |");
System.out.println("--- ================================================================= ---");
System.out.println("\tMerge Sort\t\t\t1000\t\t\t\t\t\t" + t3MS);
System.out.println("\tMerge Sort\t\t\t10000\t\t\t\t\t\t" + t4MS);
System.out.println("\tMerge Sort\t\t\t100000\t\t\t\t\t\t" + t5MS);
System.out.println("\tMerge Sort\t\t\t1000000\t\t\t\t\t\t" + t6MS);
System.out.println("\n\tShell Sort\t\t\t1000\t\t\t\t\t\t" + t3SS);
System.out.println("\tShell Sort\t\t\t10000\t\t\t\t\t\t" + t4SS);
System.out.println("\tShell Sort\t\t\t100000\t\t\t\t\t\t" + t5SS);
System.out.println("\tShell Sort\t\t\t1000000\t\t\t\t\t\t" + t6SS);
}
/**
* Mergesort method
* @param the array that is to be sorted
* @return the sorted array
*/
public static int[] mergeSort(int[] n)
{
int i;
if(n.length <= 1)
return n;
int[] leftarr = new int[(int)Math.ceil(n.length/2)];
int[] rightarr = new int[n.length-leftarr.length];
int[] result = new int[n.length];
for(i = 0; i < leftarr.length; i++)
{
leftarr[i] = n[i];
}
for(i = leftarr.length; i < leftarr.length+rightarr.length; i++)
{
rightarr[i-leftarr.length] = n[i];
}
leftarr = mergeSort(leftarr);
rightarr = mergeSort(rightarr);
result = merge(leftarr, rightarr);
return result;
}
/**
* Merge method that
*
*/
public static int[] merge(int[] left, int[] right)
{
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while(left.length > i || right.length > j)
{
if(left.length > i && right.length > j)
{
if(left[i] <= right[j])
{
result[k] = left[i];
i++;
k++;
}
else
{
result[k] = right[j];
k++;
j++;
}
}
else if(left.length > i)
{
result[k] = left[i];
k++;
i++;
}
else if(right.length > j)
{
result[k] = right[j];
k++;
j++;
}
}
return result;
}
/**
* Shell Sort
* @param the array to be sorted
* @return the sorted array
*/
public static int[] shellSort(int[] n)
{
int i, j;
int temp;
int inc = Math.round(n.length/2);
while(inc > 0)
{
for(i = 0; i < n.length; i++)
{
temp = n[i];
j = i;
while(j >= inc && n[j-inc] > temp)
{
n[j] = n[j-inc];
j = j-inc;
}
n[j] = temp;
}
inc = (int)Math.round(inc/2.2);
}
return n;
}
//n is the size
//with elements numbered from 0 to n-1
// inc ? round(n/2)
//while inc > 0 do:
// for i = inc .. n - 1 do:
// temp ? a[i]
// j ? i
// while j = inc and a[j - inc] > temp do:
// a[j] ? a[j - inc]
// j ? j - inc
// a[j] ? temp
// end for
// inc ? round(inc / 2.2)
//end while
}Could anybody suggest some better ideas???
