Zortéieralgorithmus
Vu Wikipedia, der fräier Enzyklopedie.
E Zortéieralgorithmus ass en Algorithmus, deen eng Lëscht vun Elementer (Objeten) an eng gewësse Reiefolleg bréngt. Dozou muss op dem 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 konstantem, also vun der Datequantitéit onofhängegem, Späicherbedarf auskommen, nennt een in-place. Weider ënnerscheet een tëscht stabilen an net-stabilen Zortéieralgorithmen. Bei stabilen Zortéieralgorithme bleift d'Reiefolleg vun den Datesätz, deenen hire Zortéierschlëssel gleich ass, erhalen, während net-stabil dëst net garantéieren.
Inhaltsverzeechnes |
[änneren] Allgemengt Zortéieren
Beim allgemengen Zortéiere ginn, am Géigesaz zum speziellen Zortéieren, zu der Léisung vum Zortéierproblem Vergläichsoperatiounen tëscht de Schlësselen ausgefouert.
[änneren] Beispiller
- Bubblesort (Lafzäit: O(n2), stabil, in-place)
- Heapsort (Lafzäit: O(nlogn), net-stabil, in-place)
- Mergesort (Lafzäit: O(nlogn), stabil, out-of-place)
- Quicksort (Lafzäit: O(n2), Average-Case: O(nlogn), net-stabil, in-place)
D'Lafzäit ass an der Landau-Notatioun duergestallt a bezitt sech op de schlëmmste Fall.
[änneren] Ënnescht Born fir d'allgemengt Zortéieren
[änneren] Speziellt Zortéieren
Dat speziellt Zortéiere baséiert op speziellen Eegeschafte vun den Objete fir d'Zortéierung duerchzeféieren.
[änneren] Beispiller
- Countingsort (Lafzäit: O(n + k), stabil, out-of-place)
- Bucketsort (Lafzäit: O(n + k), stabil, out-of-place)
D'Lafzäit ass an der Landau-Notatioun duergestallt a bezitt sech op de schlëmmste Fall.
[änneren] Literatur
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.
