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???

Recommended Answers

All 3 Replies

Why there are so many SIZE1???
Well, if I populate the random value, I may do it this way...

public static void main(String[] args) {
  final int SIZE1 = 100;     //constant SIZE1 for the first array
  final int SIZE2 = 1000;    //constant SIZE2 for the second array
  final int SIZE3 = 10000;   //constant SIZE3 for the third array
  final int SIZE4 = 100000;  //constant SIZE4 for the fourth array
  final int SIZE5 = 1000000; //constant SIZE5 for the fifth array
    	
  int i;  //used as a counter in the for loop
  Random gen = new Random(); //The random generator to generate
  int[] n1 = new int[SIZE1];
  int[] n2 = new int[SIZE2];
  int[] n3 = new int[SIZE3];
  int[] n4 = new int[SIZE4];
  int[] n5 = new int[SIZE5];

  for (i=0; i<SIZE5; i++) {
    if (i<SIZE1) { n1[i] = gen.nextInt(SIZE1/2)+1; }
    if (i<SIZE2) { n2[i] = gen.nextInt(SIZE2/2)+1; }
    if (i<SIZE3) { n3[i] = gen.nextInt(SIZE3/2)+1; }
    if (i<SIZE4) { n4[i] = gen.nextInt(SIZE4/2)+1; }
    n5[i] = gen.nextInt(SIZE5/2)+1; }
  }

Thats nice and short, it avoids repetition. Thanks Taywin.
I would like to ask one more question,
The shell sort I have used has the algorithm given on Wikipedia, but I was not able to figure out what is the Big Order(O), for this particular shell sort. Is it O(log^2 n)?

It is, but your implementation line 268 should be i=inc instead of i=0.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.