Part $1$: $O(n^2)$ sort

Pick a $)$ sorting algorithm $($bubble$,$ insertion, or selection$)$ and implement it in a C$++$ program to sort an array

of integers. There is C$++$ code in the textbook and online for these algorithms, but I encourage you to resist the

temptation to simply copy it$.$ Add a counter to the sort function to track the number of times that the function

accesses elements from the array you are sorting. For example, if your function has the line array$[$i$]=$ max that

counts as one array access. If your function has the line if $($array$[$i$]$ array $i+1)$ that counts as two array

accesses.

Part $2$: $O(nlogn)$ sort

Do the same thing as part $1,$ but with a O$($n log n$)$ algorithm $($merge sort or quick sort$).$

Part $3$: Counting sort

Do the same thing as part $1,$ but with the counting sort, as described here.

The counting sort can sort an array of integers that are known to be in a given range of integers by using a

second array count to count the number of occurrences of each integer in the array.

As an example, let's say we have an array called scores containing the following ten integers in the range

between $0$ and $4,$ inclusive:

scores$[]$ : $14046343$

In this case, the count array would have five elements, one for each possible value $0$ through $4.$ We initialize

count to all zeros. We then make one pass through scores $--$ each time we see a given value $x$ in scores, we

increment the value in count $x.$ When we are done, count $x$ will tell us how many instances of the value $x$ we

have in scores. In this example, count would be:

because there are $4$ zeros, $1$ one, $0$ twos, $2$ threes, $3$ fours in scores.

Once you have this array count, it is straightforward to determine the sorted scores array:

sc

and store it back into the original array.

Write a $C++$ function that implements the counting sort, assuming an array of integers that are in the range $0$ to

$100,$ inclusive.

In big O notation, what is the expected efficiency? Why is counting sort impractical as a general sorting

algorithm?