Bucketsort

Bucket Sort

whatever

Openlearnware

General information

Algorithmic problem: Sorting sequences of strings

Type of algorithm: loop

Axiliary data:

1. An ordered sequence [math]\displaystyle{ S' }[/math] of strings, which will eventually hold the overall result of the algorithm.
2. The buckets, that is, an array [math]\displaystyle{ B }[/math] whose index range contains the ID range of [math]\displaystyle{ \Sigma }[/math] (e.g. 26 for the alphabet) and whose components are ordered sequences of strings.
3. Let [math]\displaystyle{ N }[/math] denote the maximum length of an input string.
4. An array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ [1,\dots,N] }[/math] and multisets of strings as components.

Complexity

Statement: Let [math]\displaystyle{ M }[/math] denote the total sum of all input string lengths. Then the asymptotic complexity is in [math]\displaystyle{ \Theta(M) }[/math] in the best and the worst case.

Proof: Obviously, the preprocessing takes <mathO(M)</math> time. In the main loop, each character of each string is read exactly once. Obviously, no operation is applied more often than the reading of single characters.