Sorting Sequences of Strings

From Algowiki
Revision as of 11:38, 17 May 2015 by Weihe (talk | contribs) (Known algorithms)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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)