Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Felder sortieren Felder sortieren Auswahlsort

2.1 Bubblesort

Diese Sortiermethode gehört zu den einfacheren, deren Zeitverhalten proportional zum Quadrat der zu sortierenden Elemente ist. Der Algorithmus ist der Klassiker der Sortieralgorithmen und geht wie folgt:

  1. Durchwandere das Feld von dem letzten Element bis zu dem zweiten Element und tue für jedes Element folgendes:
    Ist das aktuelle Element kleiner als das Element vor ihm in dem Feld vertausche die beiden Elemente:
  2. Führe den Schritt 1 für das restliche unsortierte Feld durch, das nun ein Element weniger hat. Enthält das restliche Feld nur noch ein Element, ist das ganze Feld sortiert.

Dazu ein Beipiel mit folgenden unsortierten Feld:

3 1 2

2 ist größer als 1, keine Vertauschung

3 1 2

1 ist kleiner als 3, die beiden Elemente werden vertauscht.

1 3 2

Wir fahren mit dem um eins kleineren Rest fort.

3 2

2 ist kleiner als 3, die beiden Elemente werden vertauscht.

2 3

Das restliche Feld hat nur ein Element, wir sind fertig.

3

Der Algorithmus kann noch soweit verbessert werden, daß erkannt wird, wenn keine Vertauschung stattgefunden hat und damit das Feld schon sortiert ist. Wieso Bubblesort funktioniert, ist nicht so anschaulich zu erkennen wie bei Auswahlsort. Deshalb ist es unverständlich, wieso gerade Bubblesort zu dem Klasiker der einfachen Algorithmen geworden ist.


Home Felder sortieren Felder sortieren Auswahlsort


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum