What to do:

Setup:

In this programming assignment you will implement three sorting algorithms in Java:

1. Insertion Sort.

2. Merge Sort.

3. Quick Sort.

You are required to implement these algorithms in a singly linked list data structure, where the node elements are integers. Your main method should prompt the user to do one of these tasks:

1. Create a new list.

2. Print the list.

3. Remove an element from the list.

4. Insert an element to the list

5. Perform Insertion Sort

6. Perform Merge Sort

7. Perform Quick Sort.

8. Quit In addition to the user interface, you will run an experiment to compare the running time of the three algorithms on various input sizes(10,10^2,10^3,.....,10^7). You should have a special constructor that will generate a random list of numbers as input based on the size of the list as a parameter. Once you collect your data, fit a polynomial curve to it and provide a plot of the three curves in your submission.

Requirements:

You should at least have two classes for this assignment: LinkedList and Node.

You should allow the user to use any of the LinkedList operations.

You should perform experiments to compare the running times of the three sorting algorithms.