Question

In JAVA Find the code for sorts in your language some where online. You will copy...

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.

Homework Answers

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 :)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this...
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this assignment must be submitted by the deadline on Blackboard. Submitting your assignment early is recommended, in case problems arise with the submission process. Late submissions will be accepted (but penalized 10pts for each day late) up to one week after the submission deadline. After that, assignments will not be accepted. Assignment The object of this assignment is to construct a mini-banking system that helps...
Write a code in c++ using linear insertion following the steps below. Comment your work. 1....
Write a code in c++ using linear insertion following the steps below. Comment your work. 1.    Ask the user for the name of a file containing data. If it does not exist, the program should display an error, then ask for a new file name. Entering an asterisk (*) as the first and only character on a line should terminate the program. 2.     You can use a statically-allocated one-dimensional array of doubles for this with length 100. You...
This programming task will be a bit different. It will be more like what you would...
This programming task will be a bit different. It will be more like what you would receive if you were a maintenance engineer working in a corporate information systems or technology department. In other words, you will have some prebuilt source code provided for you that you must alter so it will meet the given programming specification.. Build a program from what you have been given as a starting-point. Rename the “starter code”. Do not add any modules; just, use...
Assignment #4 – Student Ranking : In this assignment you are going to write a program...
Assignment #4 – Student Ranking : In this assignment you are going to write a program that ask user number of students in a class and their names. Number of students are limited to 100 maximum. Then, it will ask for 3 test scores of each student. The program will calculate the average of test scores for each student and display with their names. Then, it will sort the averages in descending order and display the sorted list with students’...
JAVA Learning Objectives: To be able to code a class structure with appropriate attributes and methods....
JAVA Learning Objectives: To be able to code a class structure with appropriate attributes and methods. To demonstrate the concept of inheritance. To be able to create different objects and use both default and overloaded constructors. Practice using encapsulation (setters and getters) and the toString method. Create a set of classes for various types of video content (TvShows, Movies, MiniSeries). Write a super or parent class that contains common attributes and subclasses with unique attributes for each class. Make sure...
Take a look at the file GenericMethods.java. There are three methods you must implement: ·public static...
Take a look at the file GenericMethods.java. There are three methods you must implement: ·public static <T extends Comparable<T>> int findMin(T[] arr): Iterate through the array to find the index of the smallest element in the array. If there are two elements with the smallest value, the method should return the index of the first one. The method should run in O(n). ·public static <T extends Comparable<T>> int findMinRecursive(T[] arr): Should behave just like findMin, but should be implemented recursively....
**[70 pts]** You will be writing a (rather primitive) online store simulator. It will have these...
**[70 pts]** You will be writing a (rather primitive) online store simulator. It will have these classes: Product, Customer, and Store. All data members of each class should be marked as **private** (a leading underscore in the name). Since they're private, if you need to access them from outside the class, you should do so via get or set methods. Any get or set methods should be named per the usual convention ("get_" or "set_" followed by the name of...
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as...
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as possible: What is a checked exception, and what is an unchecked exception? What is NullPointerException? Which of the following statements (if any) will throw an exception? If no exception is thrown, what is the output? 1: System.out.println( 1 / 0 ); 2: System.out.println( 1.0 / 0 ); Point out the problem in the following code. Does the code throw any exceptions? 1: long value...
Part A. Input Validation (Name your C program yourLastName_yourFirstName_Lab4a.c) 1. Place the code you developed in...
Part A. Input Validation (Name your C program yourLastName_yourFirstName_Lab4a.c) 1. Place the code you developed in Lab 2 to obtain a diameter value from the user and compute the volume of a sphere (we assumed that to be the shape of a balloon) in a new program, and implement the following restriction on the user’s input: the user should enter a value for the diameter which is at least 8 inches but not larger than 60 inches. Using an if-else...
§ Comment your code - you will be glad you did. You will be reusing code...
§ Comment your code - you will be glad you did. You will be reusing code throughout the semester. § You will demo each of your projects. In each demo, you will be asked to demonstrate the functionality of the program and possibly describe how some of the code works. Be prepared for this. § You will upload your projects on Blackboard. Details about this will be announced in class. § Late projects will lose points: 20% per day of...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT