Task $1(30$ points$)$

In this task of the assignment, you are asked to write different sorting algorithms. The goal of the

homework is to exercise the details of sorting algorithms and have hands$-$on experience with

programming with sorting APIs.

For this assignment, you must use your own implementations of the aforementioned sorting

algorithms by taking inspiration from your textbook. You are not allowed to use any external

library or $.$jar file.

The homework consists of steps, and you should follow them sequentially, i$.$e$.$ do not go to the

next step before fixing this step. It is recommended that you complete one step per day.

Here are the steps of the homework:

Step $1.$ In this step, first write a program that $($i$)$ loads $N$ integers from a file and $($ii$)$ that creates

a random array. $($In the text file, the first line in the input file should be the size of the array, and

each following line should consist of a single integer$).$

Step $2.$ In this second step, modify the insertion sort algorithm on Page $251$ of the

textbook such that it sorts the input integer array in descending order, and start sorting the array

FROM$-$RIGHT$-$TO$-$LEFT.Step $3.$ Use the modified insertion sort algorithm on Page $251,$ now to sort an array of

float values instead of integers.

Step $4.$ Modify the top$-$down Merge Sort algorithm on page $273$ to sort the input integer

array in descending order.

Step $5.$ In this step, create a Car class. Each car should have three fields: a String attribute,

called brand, a second String attribute called modelname, a third attribute of type long,

called modelyear. The Car class should implement the Comparable interface to be able to

compare it with respect to their model years. Check the example on Page $247$ of the textbook for

implementing the Comparable interface.

Step $6.$ Modify the Quick Sort method on Page $289$ to sort the given Car objects in

descending order. For this purpose, create $10$ different Car objects, each with a different brand,

modelname, modelyear. Then, call this method to sort these objects with respect to their

modelyear's. You also need to modify QuickSort partition method $($on Page $291)$ to

reverse its sorting order.

You do not need to prepare a PDF report for this task, just document your code well.ALGORITHM $2\mathrm{.}2$ Insertion sort

For each i from $0$ to $N-1,$ exchange $a[i]$ with the entries that are smaller in a $[0]$ through a $[$i$-1].$ As

the index i travels from left to right, the entries to its left are in sorted order in the array, so the array

is fully sorted when i reaches the right end.

Trace of insertion sort $($array contents just after each insertion$)$