Algorithmen und Datenstrukturen in C/ Bubblesort

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Vorstellung[Bearbeiten]

Bubblesort ist die einfachste Art, eine Liste zu sortieren. Der Algorithmus vergleicht immer zwei nebeneinander liegende Elemente und vertauscht die beiden, falls das rechte kleiner ist als das linke. Der Name kommt daher, dass die großen Werte wie Blasen aufsteigen und nach rechts wandern.

Da nach jedem Durchlauf der Liste das größte Element ganz rechts steht, muss man nur noch eine um ein Element kürzere Liste sortieren. Somit muss man nur genauso oft durch die Liste gehen, wie sie Elemente hat.

Der Algorithmus[Bearbeiten]

void bubblesort(int *array, int length)
{
   int i, j,tmp;

   for (i = 1; i < length ; i++) 
   {
      for (j = 0; j < length - i ; j++) 
      {
          if (array[j] > array[j+1]) 
          {
              tmp = array[j];
              array[j] = array[j+1];
              array[j+1] = tmp;
          }
      }
   }
}

Laufzeit-Komplexität[Bearbeiten]

Für eine Liste mit n Elementen benötigt Bubblesort O(n²) Vergleichsoperationen.

Stabilität[Bearbeiten]

Bubblesort ist ein stabiler Sortieralgorithmus. Das bedeutet, dass in der sortierten Liste zwei gleiche Elemente in der gleichen Reihenfolge liegen wie in der unsortierten Liste.

Optimierungen[Bearbeiten]

Man kann in jedem Schleifendurchlauf prüfen, ob sich noch etwas verändert hat und dann die Sortierung abbrechen.

Um große Datenmengen schnell zu sortieren sollte man einen anderen Sortieralgorithmus verwenden, z. B. Quicksort, Mergesort oder Heapsort

<< Sortieren | Inhaltsverzeichnis | Shakersort >>