C) Bubblesort

Der Bubblesort-Algorithmus (Blasen-Sortierung) ist ein stabiler, einfacher und vor allem sehr langsamer und daher nicht zu empfehlender Sortieralgorithmus. Durch seine Einfachheit eignet er sich aber bestens für Programmieranfänger zum Nachprogrammieren und lernen.

Funktionsweise

Beim Bubblesort werden aufeinander folgende Elemente miteinander verglichen und ggf. gegeneinander ausgetauscht (falls die Reihenfolge der Werte nicht stimmt). Dabei werden alle Elemente so oft durchlaufen, bis es keine Vertauschungen mehr gibt.

Programmierung

Natürlich legen Sie wieder zuerst eine neue Klasse an. Diese Klasse enthält die öffentliche Methode bubbleSort mit keinem Rückgabewert und dem Parameter int[] (die zu sortierenden Elemente). Außerdem erstellen wir noch eine private Methode, die zwei Elemente eines int-Arrays vertauscht. Dazu benötigen wir keinen Rückgabetyp aber als Parameter das Array, in welchem getauscht werden soll, und die beiden Positionen der Elemente, die vertauscht werden sollen.

public class Sorter {

  public void bubbleSort(int[] ar) {
  }

  private void swap(int[] ar, int pos1, int pos2) {
  }
}

Der eigentliche Algorithmus – Sie haben es erraten – kommt in die bubbleSort-Methode. Zuerst kümmern wir uns aber um die swap-Methode.

Um zwei Elemente in einem Array zu vertauschen, muss das erste Element zwischengespeichert werden. Anschließend wird das erste Element durch das zweite ersetzt. Ersetzen Sie danach noch das zweite Element mit dem Zwischengespeicherten und Sie haben die Positionen getauscht.

private void swap(int[] ar, int pos1, int pos2) {
		
  int temp = ar[pos1];
  ar[pos1] = ar[pos2];
  ar[pos2] = temp;
}

Sie müssen nun folgende Punkte für den Algorithmus umsetzen:

  • Solange das komplette Array durchlaufen, bis keine Vertauschung mehr erfolgt, oder das Array „Array-Länge – 1“ mal durchlaufen wurde (maximal nötige Anzahl)
  • Jedes Element im Array mit dessen Nachbarn vergleichen.
  • Falls die Reihenfolge der Nachbarn nicht stimmt, diese vertauschen

Dies könnte z. B. so aussehen:

public void bubbleSort(int[] ar) {
		
  int arLength = ar.length;
  boolean match = false;
  for (int i = 0; i < arLength - 1 && !match; i++) {
    match = true;
    for (int j = arLength - 1; j > i; j--) {
      if (ar[j-1] > ar[j]) {
        swap(ar, j-1, j);
        match = false;
      }
    }
  }
}

Mehr ist für einen Bubblesort nicht nötig. Testen können Sie Ihren Code bspw. mit folgender main-Methode:

public static void main(String[] args) {
  int[] ar = {234,1,32,-14,6382,3,453,23,-423,0,43,1,2};
  new Sorter().bubbleSort(ar);
  for (int i = 0; i < ar.length; i++) {
    System.out.println(ar&#91;i&#93;);
  }
}&#91;/sourcecode&#93;

<strong>Zusammenfassung:</strong>

public class Sorter {
	
  public void bubbleSort(int[] ar) {
		
    int arLength = ar.length;
    boolean match = false;
    for (int i = 0; i < arLength - 1 && !match; i++) {
      match = true;
      for (int j = arLength - 1; j > i; j--) {
        if (ar[j-1] > ar[j]) {
          swap(ar, j-1, j);
          match = false;
        }
      }
    }
  }
	
  private void swap(int[] ar, int pos1, int pos2) {
		
    int temp = ar[pos1];
    ar[pos1] = ar[pos2];
    ar[pos2] = temp;
  }
}

2 Replies to “C) Bubblesort”

  1. Julian Gaal

    Wie könnte ich den Code so verändern, dass ich alle Zahlen von klein nach Groß sortiere? fpr mich als blutiger Nafänger ist der Code noch sehr schwer verständlich, aber man kann ja immer lernen…
    Über eure/deine Hilfe würde ich mich sehr freuen, Danke!

Schreibe einen Kommentar

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.