Description
As a new and eager employee of NovaTech, Inc. (Nova Technology Incorporated, a subsidiary of NSU) you've been asked by your employer to implement a sorting algorithm for inclusion in a package for a lucrative client. However, your boss just wants you to implement one of the simple, quadratic sorting algorithms. To prove that this would be a big mistake, you've decided (on your own) to prove to your idiot boss that it's worth the extra effort to implement one of the O(n log n) sorting algorithms. For this project, you will implement and compare five sorting algorithms: bubble sort, insertion sort, selection sort, quicksort, and either mergesort or shellsort.

Your main program will then do the following:
1. Ask the user for the size n of the list he/she wants to sort.
2. Create an array of size n and fill it with random integers between 1 and n. If n<=100, display the random array on the screen.
3. Run each of your sorts on this array. You must make a deep copy of the array before sorting it, or your second sort will have an easy time of it. Use the System.currentTimeMillis() function to determine the running time of each sort.
4. If n<=100, display the sorted arrays on the screen (they better be the same!).
5. Display the time each sort used to sort the array.
Once you have your program working, use it to plot a graph. Have the x-axis represent n, and the y-axis the running time. Use n=10000, 20000, ..., 100000. Plot all sorting algorithms on the same graph (use different colors or line styles). You shall use a spreadsheet program (e.g., MS Excel) or some other program to do this for you. (Will your boss be convinced?)

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.*;

/*
*/
public class Lab4 {

    // Helper method to construct random array
    public static int[] randomArray(int n) {
       int[] array = new int[n];
       for (int i = 0; i < n; i++) {
            array[i] = 1 + (int) (Math.random() * (n+1));
       }
       return array;
    }
   
    // Main method for program execution
    public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
      
       // Query the user for random array size
       System.out.println("Enter the size of the list you would like to sort: ");
       int n = Integer.parseInt(s.nextLine());
      
       // Construct random array
       int[] array = randomArray(n);
       int startTime, endTime, duration;
       Sorts.setValues(array);
       if (n <= 100) {
            System.out.println("Random Array:");
            Sorts.printValues();
       }
      
       // Do Bubble Sort
       Sorts.setValues(array);
       startTime = (int) System.currentTimeMillis();
       Sorts.bubbleSort();
       endTime = (int) System.currentTimeMillis();
       if (n <= 100) {
            System.out.println("After Bubble Sort:");
            Sorts.printValues();
       }
       duration = endTime - startTime;
       System.out.println("Bubble Sort duration: " + duration + "\n");
      
       // Do Insertion Sort
       Sorts.setValues(array);
       startTime = (int) System.currentTimeMillis();
       Sorts.insertionSort();
       endTime = (int) System.currentTimeMillis();
       if (n <= 100) {
            System.out.println("After Insertion Sort:");
            Sorts.printValues...