Difference between revisions of "Sorting Sequences of Strings"

From Algowiki
Jump to: navigation, search
(Known algorithms)
(Known algorithms)
 
Line 18: Line 18:
 
# [[Bucketsort]]
 
# [[Bucketsort]]
 
# [[Bubblesort]] (solves the [[Sorting based on pairwise comparison|generic sorting problem]])
 
# [[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]S[/math] of length [math]n \in \mathbb{N}_{0}[/math] and component type "string over some alphabet [math]\Sigma[/math]."

Output

A permutation of [math]S[/math] such that, for [math]i \in \{1,...,n-1\}[/math], [math]S[i][/math] is not lexicographically larger than [math]S[i+1][/math].

Objective

N/A

Complexity

Linear in the total sum of all string lengths.

Known algorithms

  1. Bucketsort
  2. Bubblesort (solves the generic sorting problem)
  3. Mergesort (solves the generic sorting problem)
  4. Quicksort (solves the generic sorting problem)
  5. Selection sort (solves the generic sorting problem)