Question

• Create a new class called DemoSortingPerformacne
• Create a private method called getRandomNumberArray. It returns an array of Integer and has 2 parameters:
  arraySize of type int and numberOfDigits of type int.
  This method should create an array of the specified size that is filled with random numbers.
  Each random numbers should have the same number of digits as specified in the second parameter
• In your main method (or additional private methods) do the following:
  Execute selection sort on quick sort on a number of arrays and display the time it took to sort the arrays in a tabular form as described below
  • The table should have a header line.
    Each row should display the number of elements in the array and the times in took to sort the arrays using Selection and Quick sort
  • Each row in the table should duplicate the array size of the prior row
    That means for each row a new random array of numbers needs to be created
  • Make sure to create a copy so that both sorting methods are called on the identical array.
  • The table should have at least 7 lines

Answer 1

package sort;

import java.util.Random;

public class DemoSortingPerformacne {

   public static void main(String[] args) {
       System.out.println("ArraySize\tSelection sort\t quicksort\t time taken");
       int size=4;
       for(int i=0;i<7;i++){
          
           int ar[]=getRandomNumberArray(size,3);
           long startTime = System.nanoTime();
           doSelectionSort(ar);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.print(ar.length+" "+ timeElapsed+" in NanoSec for Selection sort ");
           startTime = System.nanoTime();
           sort(ar, 0, ar.length-1);
           endTime = System.nanoTime();
           timeElapsed = endTime - startTime;
           System.out.print(" "+ timeElapsed+" in NanoSec for Quick sort");
           size*=2;
           System.out.println();
       }
   }

   public static int[] getRandomNumberArray(int arraySize ,int numberOfDigits ){
       int ar[]=new int[arraySize];
       Random rnd = new Random();
       int n = numberOfDigits + rnd.nextInt(numberOfDigits);
       for(int i=0;i<ar.length;i++){
           ar[i]=numberOfDigits + rnd.nextInt(numberOfDigits);
       }
       return ar;
   }
   public static int[] doSelectionSort(int[] placer){

   for (int index=0;index<placer.length;index++)
   {
       int smallerNumber = placer[index]; //make current element as smallest
       int smallerIn=-1; //initialize smallest index as -1
       int i=index; //define i out so that it remain accessible out side of loop
   for(;i<placer.length;i++){ //find smallest element in ar[i.....n]
         
       if(smallerNumber>placer[i]){   
           smallerNumber=placer[i];
           smallerIn=i; //remember index of smallest
       }
         
   }
   if(smallerIn!=-1){ //if smallest found
   int temp=placer[index]; //swap it
   placer[index]=smallerNumber;
   placer[smallerIn] = temp;
   }
   }
     
   return placer;
   }
   public static int part(int ar[], int l, int h)
   {
   int p = ar[l]; //to first element for array as pivote   
   int j=h; //j as highest
   int i = (h+1); //after highest index
   while (j>l) //run loop j greater the low
   {
      
   if (ar[j]>= p) { //if jth element greater then p
  
   i--; //swap ith and jth element
   int t = ar[i];
   ar[i] = ar[j];
   ar[j] = t;
   }
   j--; //go to lower element
   }   
  
   int t = ar[i-1]; //swap pivot if it is not at right place
   ar[i-1] = ar[l];
   ar[l] = t;
   return i-1;
   }
  
   public static void sort(int ar[], int l, int h)
   {
   if (l < h)
   {
       //using divide and concor
   int pi = part(ar, l, h); //find pivote index
   sort(ar, l, pi-1); //sort array before pivot
   sort(ar, pi+1, h); //after pivot
   }
   }
  
}

output

ArraySize   Selection sort   quicksort   time taken
4 3775 in NanoSec for Selection sort 6797 in NanoSec for Quick sort
8 2265 in NanoSec for Selection sort 3776 in NanoSec for Quick sort
16 4908 in NanoSec for Selection sort 14348 in NanoSec for Quick sort
32 13970 in NanoSec for Selection sort 27563 in NanoSec for Quick sort
64 45687 in NanoSec for Selection sort 91374 in NanoSec for Quick sort
128 167268 in NanoSec for Selection sort 232212 in NanoSec for Quick sort
256 654347 in NanoSec for Selection sort 137817 in NanoSec for Quick sort