InsertionSort

Wie der BubbleSort, so gehöhrt der InsertionSort zu den einfachsten Sortierverfahren. Er arbeitet wie der Ansatz, den man benutzen würde, um eine Menge von Visitenkarten zu sortieren. Man beginnt mit einem ungeordneten Stapel von Karten und mit Platz für einen zweiten Stapel, der frei bleibt. Man entfernt nun immer eine Karte von dem ungeordneten Stapel und fügt sie an der richtigen Stelle in den sortierten Stapel ein.

Formal nimmt InsertionSort ein Element von einer unsortierten Menge und fügt dieses in eine sortierte Menge ein, indem jedes Element der Menge betrachtet wird, um die richtige Stelle zu finden. Obwohl es zunächst aussieht, als ob InsertionSort Platz für die unsortierte und die sortierte Datemenge benötigt, soertiert er ``in-place''.

InsertionSort ist zwar ein einfacher Algorithmus, eignet sich jedoch wie der BubbleSort nicht für grosse Datenmengen. Dies liegt daran, dass er potentiell jedes Element einer Menge betrachten muss, um die Stelle zu finden, an die ein Element gehöhrt. Allerdings ist sein wichtiger Vorteil, dass das Einfügen eines neuen Elements nur ein einmaliges Betrachten der sortierten Elemente erfordert und nicht einen vollständigen Durchlauf des Algorithmus. Betrachtet man das Beispiel einer Schulverwaltung, die eine nach Namen sortierte Liste aller Schüler hält, die immer dann aktuallisiert, wenn ein neuer Schüller hinzugefügt wird, muss man alle Listeneinträge nur einmal betrachten, wenn man den InsertionSort benutzt.


Unterabschnitte
Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Arbeitsweise Aufwärts: Sortieren Vorherige Seite: Vergleich   Inhalt

2002-05-09