Lexikon der Mathematik: Sortieren durch Maximumsuche
allgemeines Sortierverfahren zum Sortieren von n Elementen.
Das Verfahren durchläuft n Iterationen. In der ersten Iteration berechnet es das größte Element der Eingabefolge, fügt dieses Element in die anfangs leere Ausgabefolge ein und löscht das Element aus der Eingabefolge. In der i-ten Iteration berechnet das Verfahren das größte Element der noch verbliebenen Eingabefolge, die zu diesem Zeitpunkt aus nur noch n − i + 1 Elementen besteht, fügt es an den Anfang der Ausgabefolge ein, die dann aus i Elementen besteht, und löscht es aus der Eingabefolge. Da die Berechnung des größten Elementes einer n-elementigen Menge wenigstens n − 1 Vergleiche benötigt, muß dieses Verfahren zum Sortieren von n Elementen wenigstens \(\frac{n(n-1)}{2}\) Vergleiche ausführen.
Wird in jeder Iteration jeweils das kleinste Element der Eingabefolge berechnet, so spricht man vom Sortieren durch Minimumsuche.
Schreiben Sie uns!