Part $4$: Gather efficiency data

Now, gather some data on how many array accesses these sorts require. Write a C$++$ program which declares int arrays of various lengths given in the table below, and then fills the arrays with random ints between $0$ and $100.$ Count the number of array accesses your sort algorithms from part $1,2,$ and $3$ above require to sort each array. In order to make sure you didn't hit a best case or worst case value, do at least $3$ trials. In other words, randomize the array at least $3$ times for each array length and run your sort and record the number of array accesses made. Compute the average number of array accesses for sorting each array length. For part $3,$ counting sort, you do not need to count accesses of the count array, just the array that you are sorting.

When you're finished, you should have a table like the one below, where you've filled in the number of array accesses for each pass and the average number of array accesses for your chosen sort algorithms. Observe the differences in growth between the algorithms as your $n$ gets larger.

$\backslash$table$[[\backslash$table$[[$Sort$],[$Algorithm$]],\backslash$table$[[$Array$],[$Length$]],\backslash$table$[[$Array$],[$Accesses$],[$Pass $1]],\backslash$table$[[$Array$],[$Accesses$],[$Pass $2]],\backslash$table$[[$Array$],[$Accesses$],[$Pass $3]],\backslash$table$[[$Average Array$],[$Accesses$]]],[$Bubble$,8,,,,],[$Bubble$,32,,,,],[$Bubble$,128,,,,],[$Merge$,8,,,,],[$Merge$,32,,,,],[$Merge$,128,,,,],[$Counting$,8,,,,],[$Counting$,32,,,,],[$Counting$,128,,,,]]$