Sorting Sequences of Strings: Difference between revisions
Jump to navigation
Jump to search
| (4 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
[[Category:Sorting]] | [[Category:Sorting]] | ||
==Input== | ==Input== | ||
An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n \in \mathbb{N}_{0}</math> and component type string over some [[Strings|alphabet]] <math>\Sigma</math>. | An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n \in \mathbb{N}_{0}</math> and component type "[[Strings|string]] over some [[Strings|alphabet]] <math>\Sigma</math>." | ||
==Output== | ==Output== | ||
| Line 17: | Line 17: | ||
==Known algorithms== | ==Known algorithms== | ||
# [[Bucketsort]] | # [[Bucketsort]] | ||
# [[Bubblesort]] | # [[Bubblesort]] (solves the [[Sorting based on pairwise comparison|generic sorting problem]]) | ||
# [[Mergesort]] | # [[Mergesort]] (solves the [[Sorting based on pairwise comparison|generic sorting problem]]) | ||
# [[Quicksort]] | # [[Quicksort]] (solves the [[Sorting based on pairwise comparison|generic sorting problem]]) | ||
# [[Selection sort]] | # [[Selection sort]] (solves the [[Sorting based on pairwise comparison|generic sorting problem]]) | ||
Latest revision as of 11:38, 17 May 2015
Input
An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n \in \mathbb{N}_{0} }[/math] and component type "string over some alphabet [math]\displaystyle{ \Sigma }[/math]."
Output
A permutation of [math]\displaystyle{ S }[/math] such that, for [math]\displaystyle{ i \in \{1,...,n-1\} }[/math], [math]\displaystyle{ S[i] }[/math] is not lexicographically larger than [math]\displaystyle{ S[i+1] }[/math].
Objective
N/A
Complexity
Linear in the total sum of all string lengths.
Known algorithms
- Bucketsort
- Bubblesort (solves the generic sorting problem)
- Mergesort (solves the generic sorting problem)
- Quicksort (solves the generic sorting problem)
- Selection sort (solves the generic sorting problem)