====== Bubblesort ======

Bubblesort ist ein recht einfacher, jedoch ineffizienter Sortieralgorithmus. Er basiert darauf, immer ein Element mit dem nächsten zu vergleichen. Ist das nächste Element kleiner (oder auch größer, je nach Wunsch) werden die Elemente vertauscht. Dies geschieht so lange, bis die Elemente richtig sortiert sind.\\ 

===== Implementierung =====

<code cpp>
// values: Zeiger auf zu sortierendes Array
// n: Länge des Arrays
void BubbleSort( int values[], int n )
{
  int i, j;       // Zählindizes
  int tmp;        // Hilfsvariable zum Vertauschen von Werten

  // durch das ganze Feld gehen
  for( i = 0; i < n; i++ )
  {
    // am Ende beginnen das kleinste Element zu suchen
    for( j = n - 1; j > i; j-- )
    {
      // prüfen ob das Element kleiner als der Vorgänger ist
      if( values[j] < values[j - 1] )
      {
        // Werte vertauschen
        tmp = values[j];
        values[j] = values[j - 1];
        values[j - 1] = tmp;
      }
    }
  }
}
</code>

Im obigen Beispiel kann man feststellen, dass nach einem Durchlauf das kleinste Element an der ersten Stelle des Arrays steht.

===== Verbesserungen =====

Aufgrund der vielen Vertauschungen ist Bubblesort ziemlich ineffizient. Diese lassen sich nicht vermeiden, aber mit Hilfe einiger Verbesserungen kann man die Anzahl der Vergleiche Einschränken.

==== Verbesserung 1: bereits sortiert ====

Im obigen Beispiel laufen beide Schleifen bis zum Ende, auch wenn der Array bereits sortiert ist. Selbst wenn das Feld bereits am Anfang sortiert ist wird weiter geprüft. Dieses Problem kann durch eine einfache Variable, die sich merkt ob in diesem Durchlauf etwas vertauscht wurde, umgangen werden.
Ist nach einem Durchlauf nichts mehr verändert worden, so ist das Array fertig sortiert und der Algorithmus kann vorzeitig abgebrochen werden.

<code cpp>
// values Zeiger auf zu sortierendes Array
// n Länge des Arrays
void BubbleSort( int values[], int n )
{
  int i;            // Zählindex
  int tmp;          // Hilfsvariable zum Vertauschen von Werten
  int changed;      // gibt an ob in diesem Durchlauf etwas vertauscht wurde

  do
  {
    // es wurde noch nichts vertauscht
    changed = 0;
    // am Ende beginnen das kleinste Element zu suchen
    for( i = n - 1; i > 0; i-- )
    {
      // prüfen ob das Element kleiner als der Vorgänger ist
      if (values[i] < values[i - 1])
      {
        // Werte vertauschen
        tmp = values[i];
        values[i] = values[i - 1];
        values[i - 1] = tmp;
        // es wurde etwas verändert
        changed = 1;
      }
    }
  // solange sortieren, bis nichts mehr geändert wird
  } while( changed );
}
</code>

==== Verbesserung 2: Elemente vor dem letzten Tausch bereits sortiert ====

Jene Elemente die im Array vor den zuletzt vertauschten sind (einen niedrigeren Index haben) müssen nicht mehr geprüft werden, da sie bereits sortiert sind. Im folgenden Code kombinieren wir diese und die vorhergehende Optimierung indem wir in der Variable, die vorher angab ob etwas vertauscht wurde, gleich den Index des letzten Tauschs speichern.

<code cpp>
void Bubblesort( int values[], int n )
{
  int i, j;           // Zählindizes
  int tmp;            // Hilfsvariable zum Vertauschen von Werten
  int limit;          // limit: gibt den Index des ersten unsortierten Elements an
  int lastmove;       // lastmove: Index der letzten Vertauschung
  
  // beim ersten Durchlauf ist das Limit 1,
  // d.h. alle Elemente werden geprüft
  limit = 1;
  
  do
  {
    // es wurde noch nichts vertauscht
    lastmove = 0;
    // am Ende beginnend durch den unsortierten
    // Teil des Feldes gehen
    for( int i = n - 1; i > limit; i-- )
    {
      // Wert ist kleiner als der vorhergehende
      if( values[i] < values[i - 1] )
      {
        // vertauschen
        int help = values[i];
        values[i] = values[i - 1];
        values[i - 1] = help;
        // Position der Änderung merken
        lastmove = i;
      }
    }
    // alle Elemente vor dem letzten Tausch sind bereits sortiert
    // deshalb können wir beim nächsten mal dort stoppen
    limit = lastmove + 1;
  // solange sortieren, bis nichts mehr geändert wird
  } while( lastmove != 0 );
}
</code>

==== Verbesserung 3: Sortieren von beiden Seiten ("Shakersort") ====

Weiters kann man Vergleiche sparen indem man von beiden Seiten sortiert. Zuerst wird wie gewohnt das kleinste Element ganz nach links verschoben, doch noch im selben Durchlauf das größte nach rechts. In den darauf folgenden Durchläufen sind die Orte der letzten Vertauschungen die neuen Startpunkte und Grenzen der jeweils anderen Operation.

<code cpp>
void Bubblesort( int values[], int n )
{
  int left;           // left: linker Ausgangspunkt, Startpunkt bei der Suche nach dem größten Element
                      //       Endpunkt bei der Suche nach dem kleinsten Element
  int right;          // right: rechter Ausgangspunkt, Startpunkt bei der Suche nach dem kleinsten Element
                      //        Endpunkt bei der Suche nach dem größten Element
  int lastmove;       // lastmove: speichert den Index der letzten Vertauschung
  int i;              // i: Schleifenvariable

  // Anfang des Arrays
  left = 0;
  // Ende des Arrays
  right = n - 1;
  // die letzte Vertauschung auf die Anzahl setzen; wird nichts vertauscht wird sowohl left als auch right
  // lastmove und der Algorithmus bricht ab
  lastmove = n;

  do
  {
    // von rechts nach links das kleinste Element suchen
    // und ganz nach links verschieben
    for( i = right; i > left; i-- )
    {
      // prüfen ob das Element kleiner als das vorhergehende ist
      if( values[i] < values[i - 1] )
      {
        // vertauschen
        int help = values[i];
        values[i] = values[i - 1];
        values[i - 1] = help;
        // Index der Vertauschung merken
        lastmove = i;
      }
    }
    // bis zur Vertauschung sind alle Elemente sortiert
    left = lastmove;
    // von links nach rechts das größte Element suchen
    // und ganz nach links verschieben
    for( i = left; i < right; i++ )
    {
      // prüfen ob das Element größer als das nachfolgende ist
      if( values[i] > values[i + 1] )
      {
        // vertauschen
        int help = values[i];
        values[i] = values[i + 1];
        values[i + 1] = help;
        // Index der Vertauschung merken
        lastmove = i;
      }
    }
    // nach der Vertauschung sind alle Elemente sortiert
    right = lastmove;
  // sortieren bis sich die sortierten Bereiche überschneiden oder nichts verändert wurde
  } while( left < right );
}
</code>

===== Fazit =====

Durch die vielen Verbesserungen spart man zwar Vergleiche, aber die Anzahl der viel aufwendigeren Vertauschungen bleibt gleich. Vor allem bei großen Datenmengen sind deshalb andere Algorithmen wie z. B. [[algo:selectionsort|Selectionsort]] vorzuziehen.

===== Links =====
[[http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Animation]]