Question

Step 1: Select any four sorting algorithm and two searching algorithms Step 2: Understand the logic of all the algorithms Step 3: Create java program and use your sorting/searching source codes and integrate it into your main java project. Step 4: Create a separate java class for each algorithm Step 5: Create a random function that generates at least 100000 random integer numbers from 1 to 1 million(No need to print out or store the numbers) Step 6: Insert start transaction and end transaction for each sorting and searching methods Step 7: Calculate the time in milliseconds for each sorting and searching class Step 8: Compare the performance of each algorithm

Answer 1

1. Bubble Sort

package sort;

import java.util.Random;

/*To avoid running inner loop even though array is sorted
* We can pass swapped flag inside if statement
* Initialize flag to false as not element has swapped before start swapping
* every time element get swapped set swapped flag to true
* after one iteration not single element swapped ie flag is false
* means array is swapped already no need to make another iteration
* get out of the loop
* this algorithm wont need (n^2) in best case
* in best case it perform result in even O(N) time
*/
public class BubbleSort {

   public static void bubbleSort(int ar[]){
       for(int i=0;i<ar.length;i++){
           boolean swapped=false; //for each iteration set flag =false
           for(int j=1;j<ar.length;j++){
               if(ar[j-1]>ar[j]){
                   int temp=ar[j-1];
                   ar[j-1]=ar[j];
                   ar[j]=temp;
                   swapped=true; //if swapped flag =true
               }
           }
           if(!swapped) //if not element swapped at all
               break; //array is sorted get out of loop
       }
      
   }
   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 void main(String[] args) {
       System.out.println("ArraySize\t bubbleSort sort time taken");
       int size=100000;
      
          
           int ar[]=getRandomNumberArray(size,3);
           long startTime = System.nanoTime();
           bubbleSort(ar);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.println(" in NanoSec for bubbleSort sort "+timeElapsed);

   }

}

output

NanoSec for bubbleSort sort 15305910565

2. Merge Sort

package sort;
/*worst case of merge sort is NlogN
*    Merge sort
* {20, 13, 4, 34, 5, 15, 90, 100, 75, 102}
* / \   
* {20, 13, 4, 34, 5} {15, 90, 100, 75, 102}
* / \ / \
* {20, 13, 4}{34, 5} {15, 90, 100,} {75, 102}
* / \ / \ / \ / \
*{20, 13} {4} {34} {5} {15, 90} {100} {75} {102}
* / \ / \
*{20} {13} {15} {90}
*
*Height of above tree is Log(N)
*to merge the array two temp array it will take o(N) in worst case
*so total time complexity it O(Nlog(N))
*
*/

import java.util.Random;

public class MergeSort {

   int ar[];
   MergeSort(int ar[]){
       this.ar=ar;
   }
   public static void mergeSort(int ar[],int l,int r){
       if(l<r){
           int mid=(l+r)/2; //take mid index
           mergeSort(ar,l,mid); //call mergesort on first half
           mergeSort(ar,mid+1,r); // and second half
           marge(ar,l,r,mid); //no merge the two in sorted manner
       }
   }
   public static void marge(int ar[],int l,int r,int mid){
       int t1[]=new int[mid-l+1]; //make temp array of first hlaf size and
       int t2[]=new int[r-mid]; //second half size
       int k=0; //index to 0
       for(int i=l;i<=mid;i++){ //copy fist half elements to first temp array
           t1[k++]=ar[i];
       }
       k=0;
       for(int i=mid+1;i<=r;i++){ //copy second half array to sec temp array
           t2[k++]=ar[i];
       }
       k=0;
       int k1=0; //from those two temp array copy elements in sorted array in original array
       while(k<t1.length && k1<t2.length){
           if(t1[k]<=t2[k1]){ //if t1's element is less first copy it
               ar[l++]=t1[k++];  
           }
           else{
               ar[l++]=t2[k1++]; //else t2's
           }
       }
       while(k<t1.length){ //copy the remaining elements
           ar[l++]=t1[k++];
       }
       while(k1<t2.length){
           ar[l++]=t2[k1++];
       }
   }
   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;
   }
   //driver program to test
   public static void main(String[] args) {
      
       System.out.println("ArraySize\tMerge sort time taken");
       int size=100000;
      
          
           int ar[]=getRandomNumberArray(size,3);
           long startTime = System.nanoTime();
           mergeSort(ar, 0, ar.length-1);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.print(ar.length+" "+ timeElapsed+" in NanoSec for Merge sort ");
      
   }

}

output

ArraySize   Merge sort time taken
100000 29742747 in NanoSec for Merge sort

3. Heap Sort

package sort;

import java.util.Random;

/*
* It is proved that time complexity for making heap is O(n)
* Heapify takes place in log(n)
*/

public class HeapSort {

   static int heap[];
   static int heapSize=0;
   static int OrheapSize=0;
   public static int[] makeHeapMin(int ar[],int k){
       heap=new int[ar.length];
      
       for(int i=0;i<ar.length;i++){

               heap[heapSize]=ar[i]; //first size will be zero
               OrheapSize=heapSize; //store current size
               //find correct position to store element
               //until size not equal to zero and parent element is greater then current, ,make current ele as parant
               while(heapSize!=0 && heap[getParant(heapSize)]>heap[heapSize]){
                   int temp=heap[getParant(heapSize)];
                   heap[getParant(heapSize)]=heap[heapSize];
                   heap[heapSize]=temp;
                   heapSize=getParant(heapSize);
                  
               }
                  
      
          
           heapSize=OrheapSize;
           heapSize++; //increase heap size by
       }
       return heap;
   }

   public static int getRight(int i){
       return 2*i+2;
   }
   public static int getLeft(int i){
       return 2*i+1;
   }
   public static int getParant(int i){
       return (i-1)/2;
   }
  
   public static void heapify(int i,int heap[]){
       int l=getLeft(i); //find the left index of i
       int r=getRight(i); //right index of i
       int min=i; //make ith element as minimum stroe its index
       if(l<heapSize && heap[l]<heap[min]){ //check where left element is min or not
           min=l; // if yes mark l as min
       }
       if(r<heapSize && heap[r]<heap[min]){ //same for right
           min=r;
       }
       if(min!=i){ //ith element was not min swap it with actual min
           int temp=heap[i];
           heap[i]=heap[min];
           heap[min]=temp;
           heapify(min,heap); //do recursively for next min
       }
   }

   public static int extractMin(int heap[]){
       int min=-1;
       if(heapSize<0)
           return min;
       if(heapSize==1){
           heapSize--;
           return heap[0];
       }
       else{
           min=heap[0];
           heap[0]=heap[heapSize-1];
           heapSize--;
           heapify(0,heap);
       }
       return min;
   }

   public static void printHeap(int ar[]){
       for(int i=0;i<ar.length;i++){
           System.out.print(ar[i]+" ");
       }
       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 void HeapSort(int ar[]){
       for(int i=0;i<ar.length;i++){
           extractMin(ar);
       }
   }
   public static void main(String[] args) {
      
   System.out.println("ArraySize\tSelection sort time taken");
       int size=100000;
      
          
           int ar[]=getRandomNumberArray(size,3);
           ar=makeHeapMin(ar,ar.length);
           long startTime = System.nanoTime();
           HeapSort(ar);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.print(ar.length+" "+ timeElapsed+" in NanoSec for Heap sort ");
      
  
   }
  

}

output

ArraySize   Selection sort time taken
100000 10392517 in NanoSec for Heapsort

Selection Sort

package sort;

import java.util.Random;

public class Selection {

   public static void main(String[] args) {
       System.out.println("ArraySize\tSelection sort time taken");
       int size=100000;
      
          
           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 ");
          
          
      
   }

   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;
   }
  
  
}

output
ArraySize   Selection sort time taken
100000 1645443135 in NanoSec for Selection sort

Binary Search

package search;
/*
* This is not true .
* when we doing liner search and array is sorted, we want to search max element it will take n-1 comparision
* we want to search min element it will take 1 comparison
* if array is not sorted it might take either 0 ..to .. n comparison
* that why we say in worst case time complexity of liner search O(N)
* but in Binary search max no of comparison is log(n) in worst case
* in best case one comparison
*
*/

import java.util.Random;

public class BinarySearch {
   static int c=0; //variable to count comparison
   public static int binarySearch(int ar[],int l,int r,int k){
       if(l>r) //if left greater then r element not found
           return -1;
       int mid=(l+r)/2; //find mid index
       if(ar[mid]==k){ //if mid is desired no return index
           ++c; //increase count
          
           return mid;
          
       }
       if(k<ar[mid]){ //if k less then mid element go to left array
           ++c; //increase count
          
           return binarySearch(ar,l,mid-1,k);
       }
       else{
           ++c; //if k greater then mid element go to right array
          
           return binarySearch(ar,mid+1,r,k);
       }
      
   }
  
   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;
   }
//driver program to test
   public static void main(String[] args) {
       System.out.println("ArraySize\tBinary Search time taken");
       int size=100000;
      
          
           int ar[]=getRandomNumberArray(size,3);
           long startTime = System.nanoTime();
           binarySearch(ar,0, ar.length-1, 7);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.print(ar.length+" "+ timeElapsed+" in NanoSec for Binary Search ");

   }

}

output

ArraySize   Binary Search time taken
100000 9062 in NanoSec for Binary Search

Liner Search

package search;

import java.util.Random;

public class LinerSearch {
   static int c=0; //variable to count comparison

   public static int linerSearch(int ar[],int x){
       for(int i=0;i<ar.length;i++){
           if(ar[i]==x){ //if element is x
               c++; //increase count
               return i; //return index
           }
           c++; //else increase count as element still being compared
       }
       return -1;
   }
   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;
   }
//driver program to test
   public static void main(String[] args) {
       System.out.println("ArraySize\tLiner Search time taken");
       int size=100000;
      
          
           int ar[]=getRandomNumberArray(size,3);
           long startTime = System.nanoTime();
           linerSearch(ar, 7);
           long endTime = System.nanoTime();
           long timeElapsed = endTime - startTime;
           System.out.print(ar.length+" "+ timeElapsed+" in NanoSec for Liner Search ");

   }

}

output

ArraySize   Liner Search time taken
100000 1552610 in NanoSec for Liner Search