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: ${\displaystyle {\mathcal {O}}(n^{2})}$, stabil, in-place)
• Heapsort (Lafzäit: ${\displaystyle {\mathcal {O}}(n\log n)}$, net-stabil, in-place)
• Mergesort (Lafzäit: ${\displaystyle {\mathcal {O}}(n\log n)}$, stabil, out-of-place)
• Quicksort (Lafzäit: ${\displaystyle {\mathcal {O}}(n^{2})}$, Average-Case: ${\displaystyle {\mathcal {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

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: ${\displaystyle {\mathcal {O}}(n+k)}$, stabil, out-of-place)
• Bucketsort (Lafzäit: ${\displaystyle {\mathcal {O}}(n+k)}$, 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

Commons: Sort algorithms – Biller, Videoen oder Audiodateien