Question

In JAVA

Find the code for sorts in your language some where online. You will copy code from the internet (with citation!) and modify it to test.

Make a random array of integers, then perform each search on them.

LINEAR SEARCH

Write a linear search method to find a number in the list. Call this before each of your sort methods. Include a comment explaining how Linear Search works, when to use it, when you cannot.

BINARY SEARCH

Write a binary search method to find a number in the list. Call this after each of your sort methods. Include a comment explaining how Binary Search works, when to use it, when you cannot.

BUBBLE SORT

Insert 10,000 items. Display the data before and after the sort. You’ll see that scrolling the display takes a long time. Take Screenshot Number 1 of the your changed code.

Next comment out the calls to display(). Add timing if necessary to see how long the sort itself takes. The time will vary on different machines. Take Screenshot Number 2 of your results.

Sorting 100,000 numbers will probably take less than 30 seconds. Now, select an array size that takes about this long and time it. Take Screenshot Number 3 of these results.

SELECTION SORT

Now, perform the same experiment on the Selection Sort using the same timing method you used. This will be  Screenshot Number 4, Screenshot Number 5, Screenshot Number 6.

INSERTION SORT

Now, perform the same experiment on the Selection Sort using the same timing method you used. This will be  Screenshot Number 7, Screenshot Number 8, Screenshot Number 9.

Answer 1

1) Linear Search:

In linear search, we iterate through each element and compare it with the element we want to find.
Time Complexity: O( n )
Space Complexity: O( 1 )
Linear Search is used when there are only a few elements, and we want to perform single search in unsorted list.
Linear Search is not used when the data is huge, it would take a long time to search.

import java.util.*;
import java.lang.*;
import java.io.*;

class Sample
{
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println("linear search");
        int[] a = {3,5,1,4,9,2,8,6,7};
        int number_to_be_found = 9;
        //Implementing linear search
        for(int i=0;i<a.length;i++)
            if(a[i]==number_to_be_found){
                System.out.println("Found at "+i+" index");
            }
            else{
                System.out.println("Not Found");
            }
    }
}

2) Binary Search:

Binary Search is performed on a sorted set of elements, it compares the number to be found with the middle element, if it is not the same, then it checks which (left or right) subarray will contain the element, if mid is less than element, then it would be found in right subarray, similarly for left subarray.
Time Complexity: O( log n )
Space Complexity: O( 1 )
Binary Search considerably reduces the search time if the data is sorted.
Binary search is not used when the array changes often, or if the elements are unsorted.

class BinarySearch { 
    int binarySearch(int a[], int l, int r, int number_to_be_found) 
    { 
        if (r >= l) { 
            int mid=l+(r-l)/2; 
            // checking middle element
            if (a[mid]==number_to_be_found) 
                return mid; 
            // checking left subarray 
            if (a[mid]>number_to_be_found) 
                return binarySearch(a, l, mid - 1, number_to_be_found); 
            // checking right subarray 
            return binarySearch(a, mid + 1, r, number_to_be_found); 
        } 
        // if not found
        return -1; 
    } 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int a[] = {1,2,3,4,5,6,7,8,9}; 
        int number_to_be_found = 9; 
        int result = ob.binarySearch(a, 0, a.length - 1, number_to_be_found); 
        if (result == -1) 
            System.out.println("Not found"); 
        else
            System.out.println("Found at "+result+" index"); 
    } 
} 

For the following sorts , the number of elements taken is 10.

3) Bubble Sort:

class Sample {  
  static void bubbleSort(int[] a) {  
        int n = a.length;  
        int temp = 0;  
         for(int i=0;i<n;i++)
                 for(int j=1;j<(n-i);j++) 
                          if(a[j-1]>a[j]){  
                                 //swap elements  
                                 temp = a[j-1];  
                                 a[j-1] = a[j];  
                                 a[j] = temp;  
                         }         
    }  
    public static void main(String[] args) {  
                int a[] ={2,5,7,8,4,1,3,6,9};  
                 
                System.out.println("Before Bubble Sort");  
                for(int i=0; i < a.length; i++){  
                        System.out.print(a[i] + " ");  
                }  
                System.out.println();  
                // Calling bubble sort
                bubbleSort(a);  
                 
                System.out.println("After Bubble Sort");  
                for(int i=0; i < a.length; i++){  
                        System.out.print(a[i] + " ");  
                }  
   
        }  
} 

4) Selection Sort:

class Sample {  
    public static void selectionSort(int[] a){  
        for(int i=0;i<a.length-1;i++){  
            int min = i;  
            for (int j=i + 1;j<a.length;j++)
                if (a[j]<a[min]){  
                    min = j; 
                }  
            int temp=a[min];   
            a[min]=a[i];  
            a[i]=temp;  
        }  
    }  
    public static void main(String[] args){  
        int[] a = {2,4,8,6,1,5,7,9,3};  
        System.out.println("Before Selection Sort");  
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");  
  
        System.out.println();  
          
        selectionSort(a);  
         
        System.out.println("After Selection Sort");  
        for(int i=0;i<a.length;i++) 
            System.out.print(a[i]+" ");  
    }  
} 

5) Insertion Sort:

class Sample {  
    public static void insertionSort(int a[]) {    
        for(int j=1;j<a.length;j++) {  
            int ele = a[j];  
            int i = j-1;  
            while((i >=0)&&(a[i]>ele)){  
                a[i+1] = a[i];  
                i--;  
            }  
            a[i+1] = ele;  
        }  
    }  
    public static void main(String[] args){    
        int[] a = {2,4,8,6,1,5,7,9,3};    
        System.out.println("Before Insertion Sort");    
        for(int i=0;i<a.length;i++){    
            System.out.print(a[i]+" ");    
        }    
        System.out.println();    
            
        insertionSort(a);   
           
        System.out.println("After Insertion Sort");    
        for(int i=0;i<a.length;i++){    
            System.out.print(a[i]+" ");    
        }    
    }    
} 

Please comment in case of doubts or queries.
Kindly upvote if you found it useful :)