Zortéieralgorithmus

Vu Wikipedia
Wiesselen op: Navigatioun, sichen

E Zortéieralgorithmus ass en Algorithmus, deen eng Lëscht vun Elementer (Objeten) an eng gewësse Reiefolleg bréngt. Dofir muss um Ensemble vun den Objeten eng total Uerdnung, sief et eng numeresch oder lexikographesch, definéiert sinn.

Zortéieralgorithmen, déi fir d'Zortéierung mat zousätzlechem konstanten, also vun der Datequantitéit onofhängege Späicherbedarf auskommen, nennt een in-place. Weider ënnerscheet een tëscht stabillen an net-stabillen Zortéieralgorithmen. Bei stabillen Zortéieralgorithme bleift d'Reiefolleg vun den Datesätz, deenen hiren Zortéierschlëssel d'selwecht ass, erhalen, während net-stabiller dat net garantéieren.

Allgemengt Zortéieren[änneren | Quelltext änneren]

Beim allgemengen Zortéiere ginn, am Géigesaz zum speziellen Zortéieren, fir d'Léisung vum Zortéierproblem Vergläichsoperatiounen tëscht de Schlësselen ausgefouert.

Beispiller[änneren | Quelltext änneren]

  • Bubblesort (Lafzäit: O(n^2), stabil, in-place)
  • Heapsort (Lafzäit: O(n\log n), net-stabil, in-place)
  • Mergesort (Lafzäit: O(n\log n), stabil, out-of-place)
  • Quicksort (Lafzäit: O(n^2), Average-Case: O(n\log n), net-stabil, in-place)

D'Lafzäit ass an der Landau-Notatioun duergestallt a bezitt sech op de schlëmmste Fall.

Ënnescht Born fir d'allgemengt Zortéieren[änneren | Quelltext änneren]

Speziellt Zortéieren[änneren | Quelltext änneren]

Dat speziellt Zortéiere baséiert op speziellen Eegeschafte vun den Objete fir d'Zortéierung duerchzeféieren.

Beispiller[änneren | Quelltext änneren]

D'Lafzäit ass an der Landau-Notatioun duergestallt a bezitt sech op de schlëmmste Fall.

Literatur[änneren | Quelltext änneren]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.
Commons: Sort algorithms – Biller, Videoen oder Audiodateien