Sorting - Bucket & Radix Sort

COMP202 Lectures 2022-02-18

Bucket Sort

Bucket sort is not based on comparisons but on using keys as indices of a bucket array.

1. Initially all items of the input sequence $S$ are moved to appropriate buckets.

   An item with key $k$ is moved to bucket $B[k]$.

2. Then move all items back into $S$ according to their order of appearance in consecutive buckets.

Bucket Sort Pseudo-code

• Input - A sequence $S$ of items with integer keys indexed from 0.
• Output - Sequence $S$ sorted in non-decreasing order of keys.

for each item x in S
	do
		let k be key of item x
		B[k] = remove(x,S)
for i = 0 to N - 1
	do
		for each item x in sequence B[i]
			do S = remove(x, B[i])

Radix Sort

This is an type of bucket sort that was originally used by punched card sorting machines. It can be used to sort ordered pairs into lexicographic order, where each coordinate lies in the range of integers.

In general, we can use radix sorting to sort ordered d-tuples into lexicographic ordering.

A d-tuple is a tuple with at most $d$ digits.

If words have uneven length then no letter is less than any letter: $\text{ab} < \text{abc}$.

Radix Sort Method

Sort a single column of digits, from the least to most significant digit, making $d$ passes over the data to do so.

$d$ is the number of place-values in your largest number.

We should stably sort each column. This means that if there is a tie then the original order is preserved.

Original List	$d=1$	$d=2$	$d=3$
159	742	108	108
496	125	125	125
375	496	742	159
125	896	357	357
896	357	159	496
742	108	496	742
108	159	896	896

Radix Sort Time Analysis

For a list with $n$ items and the largest number being $d$ digits long radix sort will take:

\[O(d(n+N))\]

where $N$ is $\max(n,d)$.