Algorithmen und Datenstrukturen in C/ Bubblesort

Vorstellung

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 einmal weniger durch die Liste gehen als sie Elemente hat.

Der Algorithmus

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

Für eine Liste mit n Elementen benötigt Bubblesort O(n²) Vergleichsoperationen. allSuffixes :: [a] -> a allSuffixes [] = [] allSuffixes (x:xs) = (x:xs) : allSuffixes xs

Stabilität

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

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 >>