Q1 Write a quicksort and selection sort programs that read from a file. Create a

Question

Q1 Write a quicksort and selection sort programs that read from a file. Create a data file of size 100, 1000, 10000 numbers. Run your program and report the running time for both the algorithms.

Q2 Write sequential search and binary searchprograms that read for files. Creat a data file of size 100, 1000, 1000 numbers. You will have to creat two files for each run, the first one with the numbers you want to search and the second one with numbers where you want to search the numbers. Run your program and report the running time for both the algorithms.

Explanation / Answer

import java.io.File;
import java.util.Random;
import java.util.Scanner;

public class Sorting {

   public static void main(String[] args) {
       int fact = 10;
       for(int i=0; i<3; i++){
           fact = fact*10;
           int arr[] = getArrayFromFile("random.txt",fact);
           //int arr[] = getRandom(fact);
           long start = System.currentTimeMillis();
           insertionSort(arr);
           long end = System.currentTimeMillis();
           System.out.println("Insertion Sort took "+(long)(end-start)+" mili seconds to sort "+fact+" elements ");
       }
       fact = 10;
       for(int i=0; i<3; i++){
           fact = fact*10;
           int arr[] = getArrayFromFile("random.txt",fact);
           //int arr[] = getRandom(fact);
           long start = System.currentTimeMillis();
           selectionSort(arr);
           long end = System.currentTimeMillis();
           System.out.println("Selection Sort took "+(long)(end-start)+" mili seconds to sort "+fact+" elements ");
       }
   }
   public static int[] getRandom(int size){
       Random rand = new Random();
       int[] array = new int[size];
       for(int i=1; i<= size; i++){
           array[i-1] = Math.abs(rand.nextInt())%100;
       }
       return array;
   }
   public static int insertionSort(int array[]) {
       int loopCount = 0;
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
loopCount++;
}
array[i+1] = key;
}
return loopCount;
   }
     
   public static int selectionSort(int[] arr){
       int loopCount = 0;
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;
}
loopCount++;
}
int smallerNumber = arr[index];   
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return loopCount;
}
  
   public static int[] getArrayFromFile(String filename, int size){
       Scanner sc;
       int[] array = new int[size];
       try{
           sc = new Scanner(new File(filename));

           for(int i=1; i<= size; i++){
               array[i-1] = sc.nextInt();
           }
           sc.close();
       }
       catch(Exception e){
          
       }
       return array;
   }
   public static void print(int[] array){
      
       for(int i=0; i< array.length; i++){
           System.out.print(" "+array[i]);
       }
       System.out.println();
   }
}

import java.io.File;
import java.util.Random;
import java.util.Scanner;

public class Searching {

   public static void main(String[] argv){
       int fact = 10;
       for(int i=0; i<3; i++){
           fact = fact*10;
           //int arr[] = getArrayFromFile("random.txt",fact);
           int arr[] = getRandom(fact);
           long start = System.currentTimeMillis();
           //int elements[] = getArrayFromFile("random.txt",fact);
           int elements[] = getRandom(fact);
           for(int j=0; j<elements.length; j++){
               linearSearch(arr, elements[j]);
           }
           long end = System.currentTimeMillis();
           System.out.println("Linear Search Sort took "+(long)(end-start)+" mili seconds to search "+fact+" elements in "+(fact)+" elements ");
       }
       fact = 10;
       for(int i=0; i<3; i++){
           fact = fact*10;
           //int arr[] = getArrayFromFile("random.txt",fact);
           int arr[] = getRandom(fact);
           long start = System.currentTimeMillis();
           //int elements[] = getArrayFromFile("random.txt",fact);
           int elements[] = getRandom(fact);
           for(int j=0; j<elements.length; j++){
               binarySearch(arr, elements[j]);
           }
           long end = System.currentTimeMillis();
           System.out.println("Binary Search Sort took "+(long)(end-start)+" mili seconds to search "+fact+" elements in "+(fact)+" elements ");
       }
   }
  
   public static boolean linearSearch(int[] array,int ele){
       for(int i=0; i<array.length; i++){
           if(ele==array[i])
               return true;
       }
       return false;
   }
  
   public static boolean binarySearch(int[] array,int ele){
       int s=0;
       int e=array.length-1;
       if(binarySearch(array, s, e, ele))
           return true;
       else
           return false;
   }
   private static boolean binarySearch(int[] arr, int s,int e,int ele){
       int mid = (s+e)/2;
       if(s>e)
           return false;
       if(ele > arr[mid])
           return binarySearch(arr,mid+1,e,ele);
       else if(ele < arr[mid])
           return binarySearch(arr,s,mid-1,ele);
       else
           return true;
   }
   public static int[] getArrayFromFile(String filename, int size){
       Scanner sc;
       int[] array = new int[size];
       try{
           sc = new Scanner(new File(filename));

           for(int i=1; i<= size; i++){
               array[i-1] = sc.nextInt();
           }
           sc.close();
       }
       catch(Exception e){
          
       }
       return array;
   }
   public static int[] getRandom(int size){
       Random rand = new Random();
       int[] array = new int[size];
       for(int i=1; i<= size; i++){
           array[i-1] = Math.abs(rand.nextInt())%100;
       }
       return array;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.