Bucketsort: Difference between revisions
No edit summary |
|||
(8 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Videos]] | |||
[[Category:Sorting Algorithms]] | [[Category:Sorting Algorithms]] | ||
{{#ev:youtube|https://www.youtube.com/watch?v=-POIDU_ew98|500|right|Bucketsort|frame}} | |||
== General information == | == General information == | ||
Line 16: | Line 10: | ||
'''Auxiliary data:''' | '''Auxiliary data:''' | ||
# An ordered sequence <math>S'</math> of strings, which will eventually hold the overall result of the algorithm. | # 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 | # The '''buckets''', that is, an array <math>B</math> whose index range includes the ID range of <math>\Sigma</math> (e.g. 0...127 suffices for all alphabets covered by ASCII) and whose components are [[Sets and sequences|ordered sequences]] of strings. | ||
# Let <math>N</math> denote the maximum length of an input string. | # 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. | # An array <math>A</math> with index range <math>[1,\dots,N]</math> and [[Sets and sequences|multisets]] of strings as components. | ||
Line 24: | Line 18: | ||
'''Invariant:''' After <math>i \geq 0</math> iterations: | '''Invariant:''' After <math>i \geq 0</math> iterations: | ||
# For <math>j \in \{1,\dots,N-i\}</math>, <math>A[j]</math> contains all input strings of length <math>j</math>. | # For <math>j \in \{1,\dots,N-i\}</math>, <math>A[j]</math> contains all input strings of length <math>j</math>. | ||
# <math>S'</math> contains all other input strings, that is, the ones with length at least <math>N - i + 1</math>. The sequence <math>S'</math> is sorted according to the following definition of comparison: <math>str1 | # <math>S'</math> contains all other input strings, that is, the ones with length at least <math>N - i + 1</math>. The sequence <math>S'</math> is sorted according to the following definition of comparison: <math>str1 \prec str2</math> (resp. <math>str1 \preceq str2</math>) means that the substring of <math>str1</math> starting at position <math>N - i + 1</math> is lexicographically smaller (resp., smaller or equal) than the substring of <math>str2</math> starting at position <math>N - i + 1</math>. | ||
# All buckets are empty. | # All buckets are empty. | ||
'''Variant:''' <math>i</math> increases by <math>1</math>. | '''Variant:''' <math>i</math> increases by <math>1</math>. | ||
'''Break condition: <math> | '''Break condition:''' <math>N</math> iterations are completed. | ||
== Induction basis == | == Induction basis == | ||
Line 36: | Line 30: | ||
'''Implementation:''' | '''Implementation:''' | ||
# <math>S' := \emptyset</math> | # <math>S' := \emptyset</math>. | ||
# For each <math>c \in \Sigma</math>, set <math>B[c] := \emptyset</math> | # For each <math>c \in \Sigma</math>, set <math>B[c] := \emptyset</math>. | ||
# For each <math>i \in \{1,\dots,N\}</math>, set <math>A[i] := \emptyset</math> | # For each <math>i \in \{1,\dots,N\}</math>, set <math>A[i] := \emptyset</math>. | ||
# Move each string <math>str</math> in <math>S</math> to <math>A[l(str)]</math> where <math>l(str)</math> denotes the length of <math>str</math>. | # Move each string <math>str</math> in <math>S</math> to <math>A[l(str)]</math> where <math>l(str)</math> denotes the length of <math>str</math>. | ||
Line 45: | Line 39: | ||
== Induction step == | == Induction step == | ||
'''Abstract view:''' | '''Abstract view:''' | ||
# Move each string <math>str</math> in <math>A[N-i+1]</math> to <math>B[str[N-i+1]]</math> | # Move each string <math>str</math> in <math>A[N-i+1]</math> to <math>B[str[N-i+1]]</math>. | ||
# Afterwards: Append each string <math>str</math> in <math>S'</math> at the tail of <math>B[str[N - i + 1]]</math>. It is essential that the strings are considered in the order in which they are stored in <math>S'</math>. (Now <math>S'</math> is empty.) | # Afterwards: Append each string <math>str</math> in <math>S'</math> at the tail of <math>B[str[N - i + 1]]</math>. It is essential that the strings are considered in the order in which they are stored in <math>S'</math>. (Now <math>S'</math> is empty.) | ||
# For each <math>c \in \Sigma</math> in ascending order: append <math>B[c]</math> at the tail of <math>S'</math> and make <math>B[c]</math> empty. | # For each <math>c \in \Sigma</math> in ascending order: append <math>B[c]</math> at the tail of <math>S'</math> and make <math>B[c]</math> empty. | ||
'''Implementation:''' Obvious | '''Implementation:''' Obvious. | ||
'''Correctness:''' We have to show that the relative order of each pair of strings, <math>str1</math> and <math>str2</math>, in the new sequence <math>S'</math> | '''Correctness:''' We have to show that the relative order of each pair of strings, <math>str1</math> and <math>str2</math>, in the new sequence <math>S'</math> is correct. For that, we distinguish four cases: | ||
# If <math>str1[N-i+1] \neq str2[N-i+1]</math>, <math>str1</math> and <math>str2</math> are placed in different buckets in Step 3 of the <math>i</math>-th iteration, so they are correctly ordered according to the character at position <math>N - i + 1</math>. | # If <math>str1[N-i+1] \neq str2[N-i+1]</math>, <math>str1</math> and <math>str2</math> are placed in different buckets in Step 3 of the <math>i</math>-th iteration, so they are correctly ordered according to the character at position <math>N - i + 1</math>. | ||
# If <math>str1[N-i+1] = str2[N-i+1]</math> and both strings have length <math>N - i + 1</math>, their relative order is irrelevant, so nothing is to show. | # If <math>str1[N-i+1] = str2[N-i+1]</math> and both strings have length <math>N - i + 1</math>, their relative order is irrelevant at this stage, so nothing is to show. | ||
# Next, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, one string (say, <math>str1</math>) has length <math>N - i + 1</math> and the other one (<math>str2</math>) has a length strictly greater than <math>N - i + 1</math>. Since the strings of length <math>N - i + 1</math> are placed in their buckets prior to the longer strings (cf. Steps 1 and 2), <math>str2</math> appears after <math>str1</math>, which is correct. | # Next, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, one string (say, <math>str1</math>) has length <math>N - i + 1</math> and the other one (<math>str2</math>) has a length strictly greater than <math>N - i + 1</math>. Since the strings of length <math>N - i + 1</math> are placed in their buckets prior to the longer strings (cf. Steps 1 and 2), <math>str2</math> appears after <math>str1</math>, which is correct. | ||
# Finally, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, and the lengths of both strings are larger than <math>N - i + 1</math>. Then the induction hypothesis guarantees the correct relative order due to the specific order in which the strings are considered in Step 2. | # Finally, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, and the lengths of both strings are larger than <math>N - i + 1</math>. Then the induction hypothesis guarantees the correct relative order due to the specific order in which the strings are considered in Step 2. |
Latest revision as of 22:51, 19 June 2015
General information
Algorithmic problem: Sorting Sequences of Strings
Type of algorithm: loop
Auxiliary data:
- An ordered sequence
of strings, which will eventually hold the overall result of the algorithm. - The buckets, that is, an array
whose index range includes the ID range of (e.g. 0...127 suffices for all alphabets covered by ASCII) and whose components are ordered sequences of strings. - Let
denote the maximum length of an input string. - An array
with index range and multisets of strings as components.
Abstract view
Invariant: After
- For
, contains all input strings of length . contains all other input strings, that is, the ones with length at least . The sequence is sorted according to the following definition of comparison: (resp. ) means that the substring of starting at position is lexicographically smaller (resp., smaller or equal) than the substring of starting at position .- All buckets are empty.
Variant:
Break condition:
Induction basis
Abstract view: The auxiliary data must be initialized.
Implementation:
.- For each
, set . - For each
, set . - Move each string
in to where denotes the length of .
Proof: Obvious.
Induction step
Abstract view:
- Move each string
in to . - Afterwards: Append each string
in at the tail of . It is essential that the strings are considered in the order in which they are stored in . (Now is empty.) - For each
in ascending order: append at the tail of and make empty.
Implementation: Obvious.
Correctness: We have to show that the relative order of each pair of strings,
- If
, and are placed in different buckets in Step 3 of the -th iteration, so they are correctly ordered according to the character at position . - If
and both strings have length , their relative order is irrelevant at this stage, so nothing is to show. - Next, consider the case that
, one string (say, ) has length and the other one ( ) has a length strictly greater than . Since the strings of length are placed in their buckets prior to the longer strings (cf. Steps 1 and 2), appears after , which is correct. - Finally, consider the case that
, and the lengths of both strings are larger than . Then the induction hypothesis guarantees the correct relative order due to the specific order in which the strings are considered in Step 2.
Complexity
Statement: Let
Proof: Obviously, the preprocessing takes