Question

Group Project

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

Project Deliverables

• Determine the best and worst sorting and searching algorithm
• Submit only a single word document with all the screenshots
• Java Source code
• Output screenshot that shows the transaction time for each algorithm
• 6 class files for sorting(4) and searching algorithm(2)
• 1 class file with main function
• Conclusion
• No power points only source code

Answer 1

PPLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

 ----------------------------BubbleSort.java--------------------------

// Java program for implementation of Bubble Sort

class BubbleSort

{

    // function to sort array a using bubble sort

    public void bubble_sort(int a[])

    {

        int i, j, x;

       

        for( i = 0 ; i < a.length - 1 ; i++)

        {

            for( j = 0 ; j < a.length - i - 1 ; ++j)

            {

                if (a[ j + 1 ] < a[ j ])

                {

                    // swap the j and j + 1 th element of a

                    x = a[j];

                    a[ j ] = a[ j + 1 ];

                    a[ j + 1 ] = x;

                }

            }

        }

    }

}

----------------------------------InsertionSort.java-------------------------------

import java.util.*;

public class InsertionSort

{

    public void insertion_sort(int[] a)

    {

        int i, j, temp;

       

        for (i = 1; i < a.length; i++)

        {

            // store the current element in temp

            temp = a[i];

           

            // set j to i - 1

            j = i - 1;

            // all elements greater than temp are

            // shifted 1 position right

            while (j >= 0 && a[j] > temp)

            {

                // shifted 1 position right

                a[j+1] = a[j];

                j--;

            }

           

            a[j + 1] = temp;

        }

    }

}

--------------------------------------SelectionSort.java--------------------------------

?

import java.util.*;

public class SelectionSort

{

   // sort using selection sort

    public void selection_sort(int[] a)

    {

        int i, j, min, x;

       

        // traverse the array

        for (i = 0; i < a.length - 1; i++)

        {

            // store the index of the smallest element

            min = i;

           

            // traverse the array from the element after i till the end

            for (j = i + 1; j < a.length; j++)

            {

                // if the current element is smaller than the min element

                if (a[j] < a[min])

                    min = j;

            }

            // Swap first element and min

            x = a[min];

            a[min] = a[i];

            a[i] = x;

        }

    }

}

--------------------------------------------QuickSort.java-----------------------------------------

public class QuickSort

{

    public void quick_sort(int[] arr,int p,int r)

    {

        if(p < r)

        {

            // get the partition

            int q = partition(arr,p,r);

           

            // sort left subarray

            quick_sort(arr, p, q - 1);

           

            // sort right subarray

          quick_sort(arr, q + 1, r);

        }

    }

   

    public int partition(int[] arr,int p,int r)

    {

        int i,j;

        int pivot, temp;

       

        i = p - 1;

       

        pivot = arr[r];

       

        for(j = p; j < r; j++)

        {

            if(arr[j] <= pivot)

            {

                i++;

                // swap the elements

                temp=arr[i];

                arr[i]=arr[j];

                arr[j]=temp;

            }

        }

       

        arr[r] = arr[i + 1];

        arr[i + 1] = pivot;

        return (i+1);

    }

   

}


-------------------------------------LinearSearch.java--------------------------------------

public class LinearSearch

{

    public boolean linearSearch(int[] arr , int key)

    {

        int i;

       

        for( i = 0 ; i < arr.length ; i++ )

            // if element is found

            if( arr[i] == key )

                return true;

           

        // if element is not found

        return true;

    }

}

------------------------------------BinarySearch.java---------------------------------

public class BinarySearch

{

    public boolean binarySearch(int[] arr , int p, int r, int key)

    {

        if( p < r )

        {

            int mid = ( p + r ) / 2;

           

            // if element is found

            if( arr[mid] == key )

                return true;

            // if element lies in right subarray

            else if( arr[mid] < key )

                return binarySearch(arr, mid + 1, r, key);

            // if element lies in left subarray

            else

                return binarySearch(arr, p, mid - 1, key);

        }

        // if element is not found

        else

            return false;

    }

}

----------------------------------------Test.java--------------------------------

import java.util.*;

public class Test

{

    public static void main(String[] args)

    {

        int maxSize = 100000;

        int i = 0, j = 0;

        long x;

       

        // initialize the array

        int[] a = new int[maxSize];

        int[] b = new int[maxSize];

        int[] c = new int[maxSize];

        int[] d = new int[maxSize];

       

        // fill the array with random elements

        for(j = 0; j < maxSize; j++)

        {

            int n = (int)( java.lang.Math.random()*(maxSize-1) );

            a[j] = n;

            b[j] = n;

            c[j] = n;

            d[j] = n;

        }

       

        // get the current time

        long start = System.currentTimeMillis();

       

        SelectionSort ob = new SelectionSort();

       

        // sort using bubble sort

        ob.selection_sort(a);

       

        // get the current time

        long end = System.currentTimeMillis();

       

        long time_taken = end - start;

      

        System.out.println("Time Taken for Selection Sort: " + time_taken);

       

        // Insertion Sort

           

        InsertionSort is = new InsertionSort();

       

        // get the current time

        start = System.currentTimeMillis();

       

        // sort using quick sort

        is.insertion_sort(b);

       

        // get the current time

        end = System.currentTimeMillis();

       

        time_taken = end - start;

       

        System.out.println("Time Taken for Insertion Sort: " + time_taken);

       

       

        // Bubble Sort

        BubbleSort bs = new BubbleSort();

       

        // get the current time

        start = System.currentTimeMillis();

       

        // sort using bubble sort

        bs.bubble_sort(c);

       

        // get the current time

        end = System.currentTimeMillis();

       

        time_taken = end - start;

       

        System.out.println("Time Taken for Bubble Sort : " + time_taken);

       

       

        // QuickSort

        QuickSort qs = new QuickSort();

       

        // get the current time

        start = System.currentTimeMillis();

       

        // sort using quick sort

        qs.quick_sort(d, 0, d.length - 1);

       

        // get the current time

        end = System.currentTimeMillis();

       

        time_taken = end - start;

       

        System.out.println("Time Taken for quick sort : " + time_taken);

       

       

        // search algoithms

        // create a Random object

        Random rand = new Random();

       

        // create a Random object

        Scanner sc = new Scanner(System.in);

       

        System.out.print("Enter n : ");

        int n = sc.nextInt();

       

        int[] arr = new int[n];

       

        for( i = 0 ; i < n ; i++ )

            arr[i] = rand.nextInt( 1000 - ( -1000 ) + 1 ) - 1000;

       

        int key = 5000;

       

        LinearSearch ls = new LinearSearch();

       

        // get the current time

        long start_linear = System.currentTimeMillis();

       

        boolean flag1 = ls.linearSearch(arr, key);

       

        // get the current time

        long end_linear = System.currentTimeMillis();

       

        long time_linear = end_linear - start_linear;

       

        BinarySearch bs1 = new BinarySearch();

       

        // get the current time

        long start_binary = System.currentTimeMillis();

       

        boolean flag2 = bs1.binarySearch(arr, 0, arr.length, key);

       

        // get the current time

        long end_binary = System.currentTimeMillis();

       

        long time_binary = end_binary - start_binary;

       

        System.out.println("Time Taken for Linear Search ; " + time_linear);

        System.out.println("Time Taken for Binary Search ; " + time_binary);

    }

}