• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Übersicht über Sortieralgorithmen

Contents

  • Vergleichsbasiert
  • Nicht Vergleichsbasiert
  • Siehe auch

Eine Übersicht über gängige Sortieralgorithmen:

Vergleichsbasiert

Name Laufzeit stabil in-place
B AVG W
Selectionsort $\Theta (n^2)$ $\Theta (n^2)$ $\Theta (n^2)$ ✘[1] ✔
Bubblesort $\Theta (n)$ $\cal{O}(n^2)$ $\Theta (n^2)$ ✔ ✔
Insertionsort $\Theta (n)$ $\Theta (n^2)$ $\Theta (n^2)$ ✔ ✔
Quicksort $\Theta (n \cdot \log(n))$ $\Theta (n \cdot \log(n))$ $\Theta (n^2)$ ✘ ✔
Heapsort $\cal{O}(n \cdot \log(n))$ $\cal{O}(n \cdot \log(n))$ $\cal{O}(n \cdot \log(n))$ ✘ ✔
Mergesort $\Theta (n \cdot \log(n))$ $\Theta (n \cdot \log(n))$ $\Theta (n \cdot \log(n))$ ✔ ✘[2]
Timsort $\Theta (n)$ $\cal{O}(n \cdot \log(n))$ $\cal{O}(n \cdot \log(n))$ ✔ ✘

Ich habe - bis auf Timsort - jeden dieser Algorithmen in Python implementiert, siehe Python-Code für Sortieralgorithmen.

[1]: Beispiel: A = [2, 2, 1] [2]: in der regel nicht in-place, kann aber auch in-place implementiert werden.

Nicht Vergleichsbasiert

Es sei

  • $n$ die Anzahl der Zahlen,
  • $d$ die maximale Anzahl der Stellen
  • $k$ die Anzahl der möglichen Zeichen (die Basis).

Dann gilt:

Name Worst-Case Laufzeit stabil in-place
Radixsort $\cal{O}(d \cdot (n+k))$ ✔ ✘
Countingsort $\cal{O}(n+k)$ ✔ ✘

Siehe auch

  • Sorting Algorithm Animations: Eine tolle Website, die veranschaulicht, wie verschiedene Sortieralgorithmen funktionieren.
  • What different sorting algorithms sound like

Published

Jul 15, 2012
by Martin Thoma

Category

German posts

Tags

  • algorithms 13
  • Big-O 3
  • sorting 3

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor