Bucketsort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/bucket-sort-1941 Openlearnware]</div> | <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/bucket-sort-1941 Openlearnware]</div> | ||
</div> | </div> | ||
== General information == | |||
'''Algorithmic problem:''' [[Sorting sequences of strings]] | |||
'''Type of algorithm:''' loop | |||
'''Axiliary data:''' | |||
# An ordered sequence <math>S'</math> of strings, which will eventually hold the overall result of the algorithm. | |||
# The '''buckets''', that is, an array <math>B</math> whose index range contains the ID range of <math>\Sigma</math> (e.g. 26 for the alphabet) and whose components are [[Sets and sequences|ordered sequences]] of strings. | |||
# Let <math>N</math> denote the maximum length of an input string. | |||
# An array <math>A</math> with index range <math>[1,\dots,N]</math> and [[Sets and sequences|multisets]] of strings as components. | |||
== Abstract view == | |||
== Induction basis == | |||
== Induction step == | |||
== Complexity == | |||
Revision as of 21:35, 2 October 2014
General information
Algorithmic problem: Sorting sequences of strings
Type of algorithm: loop
Axiliary data:
- An ordered sequence [math]\displaystyle{ S' }[/math] of strings, which will eventually hold the overall result of the algorithm.
- 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.
- Let [math]\displaystyle{ N }[/math] denote the maximum length of an input string.
- An array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ [1,\dots,N] }[/math] and multisets of strings as components.