Create a dynamic array of size n and populate it with numbers from $1$ to n$.$

Shuffle the numbers in the array.

Run the selection sort, bubble sort, merge sort, and quick sort on the array to sort the shuffled numbers in increasing order.

Count, for each of the sorting algorithms mentioned above, the number of comparisons and the number of data exchanged in the algorithms.

Repeat steps $2$ to $4$ for $100$ times.

Output the average number of comparisons and the average number of data exchange made for each sorting algorithm.

Define and implement a better algorithm to sort the list based on the data and do steps $2$ and $4$ for $100$ times.

Output the average number of comparisons and the average number of data exchange made for your algorithm.

Your program should start with reading an integer, n$,$ from the user.