Sorting Sequences of Strings: Difference between revisions

From Algowiki
Jump to navigation Jump to search
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 "string over some [[Strings|alphabet]] <math>\Sigma</math>."


==Output==
==Output==

Revision as of 11:36, 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

  1. Bucketsort
  2. Bubblesort
  3. Mergesort
  4. Quicksort
  5. Selection sort