Using Figure 8.4 as a model, illustrate the operation of \(\textsc{Bucket-Sort}\) on the array \(A = \langle .79, .13, .16, .64, .39, .20, .89, .53, .71, .42 \rangle\).
We have \(n = 10\) elements, so we create 10 buckets indexed from 0 to 9. Each element goes into bucket \(\lfloor n \cdot A[i] \rfloor = \lfloor 10 \cdot A[i] \rfloor\).
Step 1: Distribute elements into buckets
For each element, calculate its bucket index:
- \(A[1] = .79 \rightarrow\) bucket \(\lfloor 10 \times .79 \rfloor = 7\)
- \(A[2] = .13 \rightarrow\) bucket \(\lfloor 10 \times .13 \rfloor = 1\)
- \(A[3] = .16 \rightarrow\) bucket \(\lfloor 10 \times .16 \rfloor = 1\)
- \(A[4] = .64 \rightarrow\) bucket \(\lfloor 10 \times .64 \rfloor = 6\)
- \(A[5] = .39 \rightarrow\) bucket \(\lfloor 10 \times .39 \rfloor = 3\)
- \(A[6] = .20 \rightarrow\) bucket \(\lfloor 10 \times .20 \rfloor = 2\)
- \(A[7] = .89 \rightarrow\) bucket \(\lfloor 10 \times .89 \rfloor = 8\)
- \(A[8] = .53 \rightarrow\) bucket \(\lfloor 10 \times .53 \rfloor = 5\)
- \(A[9] = .71 \rightarrow\) bucket \(\lfloor 10 \times .71 \rfloor = 7\)
- \(A[10] = .42 \rightarrow\) bucket \(\lfloor 10 \times .42 \rfloor = 4\)
Buckets after distribution:
- \(B[0]\): empty
- \(B[1]\): .13, .16
- \(B[2]\): .20
- \(B[3]\): .39
- \(B[4]\): .42
- \(B[5]\): .53
- \(B[6]\): .64
- \(B[7]\): .79, .71
- \(B[8]\): .89
- \(B[9]\): empty
Step 2: Sort each bucket using insertion sort
- \(B[1]\): .13, .16 (already sorted)
- \(B[7]\): .79, .71 \(\rightarrow\) .71, .79
Step 3: Concatenate buckets in order
\[[.13, .16, .20, .39, .42, .53, .64, .71, .79, .89]\]The array is now sorted! Notice how most buckets contain 0 or 1 element, making the insertion sort step trivial. This is typical when the input is uniformly distributed.