Zortéieralgorithmus

E Zortéieralgorithmus ass en Algorithmus, deen eng Lëscht vun Elementer (Objeten) an eng gewësse Reiefolleg bréngt. Dofir muss um Ensembel 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ärend net-stabiller dat net garantéieren.

 Allgemengt Zortéieren 
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 
 Bubblesort (Lafzäit: , stabil, in-place)
 Heapsort (Lafzäit: , net-stabil, in-place)
 Mergesort (Lafzäit: , stabil, out-of-place)
 Quicksort (Lafzäit: , Average-Case: , 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 

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

 Beispiller 
 Countingsort (Lafzäit: , stabil, out-of-place)
 Bucketsort (Lafzäit: , stabil, out-of-place)
D'Lafzäit ass an der Landau-Notatioun duergestallt a bezitt sech op de schlëmmste Fall.

 Literatur 
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.

 Um Spaweck 

Kategorie:Algorithmen