Question

Write a Java program using the OOP paradigm to do the following:

1. Main Function: create a list with a million items, and you can use the generate function to add a million random values to the list.

2. Create a method to sort the list created in the main function using bubble sort, then use the sorted list to search for the (k) value using binary search.

3. Create a method to create a new list of 1000 items and search for a value (V) using linear search.

4. Create a method to create a new list of 77 items and then sort it using the selection sort.

Answer 1

import java.util.Random;

public class Sorting {

    public static int sortBinarySearch(int array[], int k){

        // Sort array using bubble sort

        int n = array.length;
        for (int i = 0; i < n-1; i++){
            for (int j = 0; j < n-i-1; j++){
                if (array[j] > array[j+1]){
                // swap temp and arr[i]
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }


        // Search for the element using binary search.
        // Iterative binary search is used.

        int l = 0;
        int r = n-1;

        while(l <= r){
            int mid = (l + r)/2;
            if(array[mid] == k){
                return mid;
            }
            else if(array[mid] > k){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }

        return -1;

    }

    public static int linearSearch(int v){

        // Create a random array of 1000 elements
        Random rand = new Random();

        int n = 1000;
        int array[] = new int[n];

        for(int i=0;i<n;i++){
            array[i] = rand.nextInt();
        }

        // Linear search for v
        for(int i=0;i<n;i++){
            if(array[i] == v){
                return i;
            }
        }

        return -1;
    }

    public static void selectionSort(){

        // Create a random array of 77 elements.
        Random rand = new Random();

        int n = 77;
        int array[] = new int[n];

        for(int i=0;i<n;i++){
            array[i] = rand.nextInt();
        }

        // Selection sort -  iteratively find the next minimum element and place it in the front of array,
        for (int i = 0; i < n-1; i++){
        
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (array[j] < array[min_idx])
                    min_idx = j;
 
            // Swap the found minimum element with the first
            // element
            int temp = array[min_idx];
            array[min_idx] = array[i];
            array[i] = temp;
        }

        

    } 

    public static void main(String[] args){

        // Make a random array of 1000 elements.
        Random rand = new Random();

        int n = 1000000;
        int array[] = new int[n];

        // Random element is filled.
        // Use rand.nextInt(bound) to restrict the random numbers to a bound.
        for(int i=0;i<n;i++){
            array[i] = rand.nextInt();
        }

       // Calling methods.
       int index = sortBinarySearch(array, 100);
       
       System.out.println(index);

       int index2 = linearSearch(500);

       selectionSort();


    }
    
}

I cannot show the output as the first method where we do bubble sort does not complete in a reasonable amount of time. It can take a couple of hours to sort an array of million elements using bubble sort.

I have added comments for your understanding

I would love to resolve any queries in the comments. Please consider dropping an upvote to help out a struggling college kid :)

Happy Coding !!