Sorting Sequences of Strings

From Algowiki
Revision as of 11:38, 17 May 2015 by Weihe (talk | contribs) (Known algorithms)
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
  4. Quicksort
  5. Selection sort