Question $9$

$2$ pts

Bucket Sort

A bucket sort algorithm requires that the input is taken from a uniform distribution of numbers and has an average$-$case running time of $O(n).$ So$,$ depending on the distribution of numbers, it may perform worse then $O(n).$

Here is the pseudocode of the bucket sort algorithm:

Make a hash table with a chain resolution

Use the hash function that assigns most significant digits to 'a bucket', a hash table entry, i$.$e$.,$ a hash table index $=$ floor $(nA[i]),$ where $n$ is a number from $0$ to the size of the input array, $A[i]$ is an item in the input array $A.$ For example, $A=[0\mathrm{.}1,3\mathrm{.}05,2\mathrm{.}879]$ then the index of $0\mathrm{.}1$ is floor $(30\mathrm{.}1)=$ floor $(0\mathrm{.}3)=0,$ the index of $34$ is floor $(33\mathrm{.}05)=9,$ the index of $2\mathrm{.}879$ is $8.$

Sort lists that are created by the chain resolution using insertion sort.

Best running time

Worst running time

Average running time