Sorting Sequences of Strings: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(3 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

  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)