CoutingSort

Eine spezielle aber durchaus häufig auftretende Situation entsteht, wenn eine Menge, die aus numerischen Werten besteht, zu sortieren ist. Genauer beschrieben handelt es sich um eine Menge, deren Elemente durch numerische Werte representiert werden können und auf Grund deren Wertigkeit sortiert werden sollen. Ein effizienter und einfacher Algorithmus, der jedoch nur bei dieser Gegebenheit der Elemente funktioniert, ist der CountingSort, welcher auch oft als Distribution Counting bezeichnet wird.

Dieser Algorithmus verwendet zusätzlichen Speicher und schafft die Sortierung in linearer Zeit. Wie bei anderen Algorithmen, kann auch hier die Implementierung so gewählt werden, damit die Notwendigkeit des zusätzlichen Speichers wegfällt. Jedoch tritt hier das Problem ``Speicher gegen Laufzeit'' zutage.


Unterabschnitte
Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Bedingungen Aufwärts: Sortieren Vorherige Seite: Implementierung   Inhalt

2002-05-09