Implement in Java two versions of the Quicksort algorithm: HOARE$-$QUICKSORT and Lomuto$-$Quicksort. Please follow the pseudocode for these two algorithms discussed in class, which can be found on the Module $2-$ Part $2$ lecture slides. Please make sure that your implementations will correctly sort any input array into ascending $($non$-$decreasing$)$ order.

For each of these two versions of Quicksort algorithms, please add two static counters to your program, one to track the number of key comparisons $($KCs$)$ and the other to track the number of swaps. The output of your program should include the total number of KCs and the total number of swaps made by each Quicksort algorithm. To check your program's correctness, you can run it on small input arrays, such as the examples we discussed in class.

Complete the Following Tasks:

a$.$

Programming. Submit one $.$zip file including all source files of your program for grading. You will get $0$ points for this part if your program does not compile.

b$.$

Run your program multiple times on different input arrays as outlined in the first two columns of the following table. Fill in the table $($at the top of the following page$)$ with data obtained from your program's outputs. Additionally, include screenshots capturing your program's output for each run.

c$.$

Based on the results you obtained in part b$,$ does one version of the Quicksort algorithm always perform better $($better means with fewer KCs AND also fewer swaps$)$ than the other? If your answer is no$,$ in which of the four case$($s$)$ does one Quicksort algorithm perform better than the other?

$2$

$\backslash$table$[[$Input array,Hoare$-$Quicksort,Lomuto$-$Quicksort$],[$Array elements,Size,# of $KCs,$# of Swaps,# of $KCs,$# of Swaps$],[\backslash$table$[[(1)$ Distinct numbers in$],[$ascending order$]],100,,,,],[1,000,,,,],[10,000,,,,],[\backslash$table$[[(2)$ Distinct numbers in$],[$descending order$]],100,,,,],[1,000,,,,],[10,000,,,,],[(3)$ All the same number,$100,,,,],[1,000,,,,],[10,000,,,,],[\backslash$table$[[(4)$ Random numbers between$],[1$ and $100,000,$ inclusive$]],100,,,,],[1,000,,,,],[10,000,,,,]]$