Consider the two algorithm optimization proposals QuickSortOpt1 and QuickSortOpt2, described below. QuickSortOpt1 executes QuickSort until partitions size gets lower than a given cutoff value (usually 10) and then, executes InsertSort for sorting the small partitions. QuickSortOpt2 executes QuickSort until partitions size gets lower than a given cutoff value (usually 10) and then, executes InsertSort on the whole "almost sorted" array. 

Design and implement a Java program which defines an array of size SIZE, randomly populated with Integer or int values in the range 1 .. MAXRNG and sorts the array in increasing order of its values using QuickSortOpt1 and then by QuickSortOpt2. Consider two program execution cases defined by the value of the boolean constant SHOW. 
a) (SHOW value is true). The program should display the array values before sorting and then after invoking each sorting method. For this case, consider SIZE value 100 and MAXRNG value 9999. 
b) (SHOW value is false). Measure the execution time of the three sorting algorithms using System.nanoTime() method and display their average values for 10 runs (array values should not be shown). Fill-in the table below with the measured values considering SIZE value 100,000 and MAXRNG value 999,999. Discuss the results. 
Algorithm Measured mean values of the execution time 

QuickSortOpt1
QuickSortOpt2
2. Deliverables 
a) All .java source files. 
b) Screenshots showing program execution and the results of your testing. 

Consider a user interface menu using doubly linked lists as main data structures. 
The menu consists of a set of main menu items, each main menu item having associated a submenu consisting of a set of submenu items (see the example in the attached file). 

The set of main menu items should be implemented as a doubly linked list of mNodes, each mNode representing a main menu item. Each mNode defines the main menu item name, two links to its mNode neighbors (the previous and next mNode) and a link to its first submenu node. 
Each submenu should be implemented as a doubly linked list of smNodes. Each smNode contains its name and two links to its smNode neighbors (the up and down smNode). 
The data structures of a particular user interface menu are shown in the attached file. 
Your task is to design, write and test a java program Menu.java executing the following tasks: 
a) Read a menu from an input file Menu.txt and build the linked lists data structures. Each file line contains a main menu item followed by its submenu items, all items being separated by the semicolon character. 
Example of input file content: 
File;New;Open;Save;SaveAs;Close 
View;Color;Gray;Zoom;Ruler;Grid 
Process;Select;Move;Rotate;Scale;Delete;Group 
About;Release;Version;Contact;Description 
b) Traverse the linked lists data structures and display the menu, using the same format as the one in the input file. The main menu items and the submenu items will be traversed in forward direction. 
c) Add a new main menu item and its associated submenu to the existing menu. Read the new main menu item data from an input file MenuAdd.txt. The input file contains two lines. The first line specifies the main menu node after which the new main menu node will be inserted. The second line specifies the new main menu node and its submenu nodes. Display the menu after adding the new main menu item. The main menu items will be traversed in backwards direction while the submenu items will be traversed in forward direction. 
Example of adding a new menu item 

For example, the file content below specifies that the new main menu item called Layout (with submenu items Margins, Orientation and Size) will be inserted into the existing menu after the main menu item View. 
View 
Layout;Margins;Orientation;Size 
d) Ask the user to enter the name of a main menu item and remove it from the menu. Traverse the linked lists data structures (in the same direction as of question b)) and display the menu after the remove operation was performed.