Question

1.) Generate an array of 10 random numbers between 1 - 100 2.) Copy the array to a temp array 3.) Call each of the methods to sort (bubble, selection, insertion, quick, merge), passing it the array 4.) In-between the calls, you are going to refresh the array to the original numbers. 5.) Inside of each sorting method, you are going to obtain the nanoseconds time, before and after the method Subtract the before time from the after time to obtain total time in nanoseconds 6.) Display the amount of time that the sort took 7.) Tell me which sort was fastest.

help please this is java please use simple code

Answer 1

Program: In this program, we have calculate the time taken by different sorting algorithms on an unsorted array of size 10 which contains random number in the range 1-100. We calculate the time of each algorithm in nanoseconds, and keep updating the minimum time among all. Then we print our result.

Code:

class Solution {
    public static void main(String[] args) {

        // Create an array of size 10
        int[] array = new int[10];
        // Fill array with random integers from 1-100
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 100) + 1;
        }

        // Create temp array of size same as above
        int[] temp = new int[array.length];

        // Copy temp array to array
        copy(temp, array);

        // Variables to store minimum time algo name
        String minimumTimeAlgo = "";
        long min = Integer.MAX_VALUE;

        // Call Bubble sort and calculate time
        System.out.println("Calling Bubble Sort..");
        long startTime1 = System.nanoTime();
        bubbleSort(temp);
        long endTime1 = System.nanoTime();
        System.out.println("Time taken: " + (endTime1 - startTime1) + " ns");
        if (endTime1 - startTime1 < min) {
            min = endTime1 - startTime1;
            minimumTimeAlgo = "BubbleSort";
        }

        // Copy temp back to original array
        copy(temp, array);

        // Call Selection sort and calculate time
        System.out.println("\nCalling Selection sort..");
        long startTime2 = System.nanoTime();
        selectionSort(temp);
        long endTime2 = System.nanoTime();
        System.out.println("Time taken: " + (endTime2 - startTime2) + " ns");
        if (endTime2 - startTime2 < min) {
            min = endTime2 - startTime2;
            minimumTimeAlgo = "SelectionSort";
        }
        // Copy temp back to original array
        copy(temp, array);

        // Call Insertion sort and calculate time
        System.out.println("\nCalling Insertion Sort..");
        long startTime3 = System.nanoTime();
        insertionSort(temp);
        long endTime3 = System.nanoTime();
        System.out.println("Time taken: " + (endTime3 - startTime3) + " ns");
        if (endTime3 - startTime3 < min) {
            min = endTime3 - startTime3;
            minimumTimeAlgo = "InsertionSort";
        }
        // Copy temp back to original array
        copy(temp, array);

        // Call Quick sort and calculate time
        System.out.println("\nCalling Quick Sort..");
        long startTime4 = System.nanoTime();
        quickSort(temp, 0, temp.length - 1);
        long endTime4 = System.nanoTime();
        System.out.println("Time taken: " + (endTime4 - startTime4) + " ns");
        if (endTime4 - startTime4 < min) {
            min = endTime4 - startTime4;
            minimumTimeAlgo = "QuickSort";
        }
        // Copy temp back to original array
        copy(temp, array);

        // Call Merge sort and calculate time
        System.out.println("\nCalling Merge Sort..");
        long startTime5 = System.nanoTime();
        mergeSort(temp, 0, temp.length - 1);
        long endTime5 = System.nanoTime();
        System.out.println("Time taken: " + (endTime5 - startTime5) + " ns");
        if (endTime5 - startTime5 < min) {
            min = endTime5 - startTime5;
            minimumTimeAlgo = "MergeSort";
        }
        // Copy temp back to original array
        copy(temp, array);

        // Print results of minimum time
        System.out.println("\nMinimum time taken by " + minimumTimeAlgo + ": " + min + " ns");

    }

    // Method to copy temp to array
    public static void copy(int[] temp, int[] array) {
        for (int i = 0; i < array.length; i++) {
            temp[i] = array[i];
        }
    }

    // Method to Quick Sort
    public static void quickSort(int array[], int low, int high) {
        if (low < high) {

            int pi = partition(array, low, high);

            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    // Method to partition array
    public static int partition(int array[], int low, int high) {

        int pivot = array[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {

            if (array[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }


    // Method to merge sort
    private static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int mid = l + (r - l) / 2;
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, r, mid);
        }
    }

    // Merge method
    public static void merge(int[] arr, int l, int r, int mid) {

        int n = mid - l + 1;
        int m = r - mid;
        int[] left = new int[n];
        int[] right = new int[m];

        for (int i = 0; i < n; i++) {
            left[i] = arr[i + l];
        }

        for (int i = 0; i < m; i++) {
            right[i] = arr[mid + i + 1];
        }

        int i = 0, j = 0, k = l;
        while (i < n && j < m) {
            if (left[i] < right[j]) {
                arr[k] = left[i];
                k++;
                i++;
            } else {
                arr[k] = right[j];
                k++;
                j++;
            }
        }
        while (i < n) {
            arr[k] = left[i];
            k++;
            i++;
        }
        while (j < m) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    // Bubble sort
    public static void bubbleSort(int[] array) {
        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 arr[j+1] and arr[i]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }


    // Selection sort
    public static void selectionSort(int array[]) {

        int n = array.length;

        for (int i = 0; i < n - 1; i++) {

            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (array[j] < array[min_idx])
                    min_idx = j;

            int temp = array[min_idx];
            array[min_idx] = array[i];
            array[i] = temp;
        }
    }

    // Insertion Sort
    public static void insertionSort(int array[]) {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;

            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }
}

Output:

#Please ask for any doubts. Thanks.