Standard Bubblesort

Einer der allerersten Algorithmen, welche gelernt werden ist der Bubblesort.

Der Bubblesort wird dazu verwendet um z.B. ganze Zahlen (Typ Integer) in einem Array zu sortieren.
Es gibt wesentlich effizientere Methoden um ein Array zu sortieren. Da die Auszubildende Person aber auch per Hand wissen sollte wie das funktioniert habe ich den oder die Auszubildende diesen Algorithmus erstellen lassen. Alleine schon um die Fähigkeit Probleme zu lösen, die Herangehensweise zu erlernen.

Hier beschreibe ich eine von vielen Lösungen (vielleicht nicht die Beste, aber eine Lösung).

In diesem Beispiel verwenden wir eine Funktion für den Bubblesort Algorithmus, wir übergeben der Funktion einen ungeordneten Array und erhalten dann ein geordneten Array zurück.

public int[] BubbleSort(int[] arr)
        {
            int temp;//temporärer Integer

            for (int j = 0; j <= arr.Length - 2; j++)
            {
                for (int i = 0; i <= arr.Length - 2; i++)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        temp = arr[i + 1];
                        arr[i + 1] = arr[i];
                        arr[i] = temp;
                    }
                }
            }
            return arr;
        }

Was macht die Funktion?

Übergeben wird ein Array z.B. mit folgenden Einträgen { 1, 6, 2, 4, 9, 7, 3, 5, 9, 8 }.
Die erste for Schleife (j) wiederholt 8x den Sortiervorgang (das Array hat 10 Einträge die letzten 2 sind aber nach den 8 Durchläufen schon sortiert, das spart Zeit (im Thema Mulitheading werde ich anhand des Bubblesorts beschreiben warum Zeit ein wichtiges Thema ist).

Initialzustand des ArrayLauf 1Lauf 2Lauf 3Lauf 4Lauf 5Lauf 6Lauf 7Lauf 8Rückgabe
1111111100
6222222011
2444330222
4663403333
9735044444
7350555555
3506666666
5077777777
0888888888
8999999999
Wie der Bubblesort sortiert
  • (j=0) Während des ersten lauf, wird die 6 solange weitergeschoben bis die 6 vor der 7 ist, (im Code if (arr[i] > arr[i + 1]) , 6 ist kleiner 7. Wenn die 6 hochgeschoben wird, wird die Zahl welche die 6 ersetzt an der ehemaligen stelle der 6 gesetzt. Der erste lauf wird sooft durchgeführt bis auch die Arraylänge -2 (hier in diesem Fall 8 mal) durchgeführt.
  • (j=1) Wie bei j=0 genauer beschrieben, wird im 2ten Lauf (auch 8x) weiter die Ziffern gerückt.
  • Dies führt sich nun so fort.
  • (j=8) Oben in der Tabelle zu sehen, erhalten erst beim letzten lauf alle Zahlen ihre korrekte Position. Jetzt hat die Funktion sortiert und gibt ein ordentlich sortiertes Array zurück.

Nun kommen wir zur einfachen Methode, das .NET Framework bietet hier Funktionen an, ein Beispiel:

int[] arInt = new int[] { 1, 6, 2, 4, 9, 7, 3, 5, 0, 8 };
var geordnet = arInt.OrderBy(x => x);
/* in var geordnet sind die zahlen wie bei der selbstgeschriebenen Funktion Bubblesort sortiert.
*/

Der Bubblesort gehört zum Grundwissen eines Programmierers und sollte jeder aus dem FF schreiben können. Effizienter ist der Quicksort Algorithmus.

Nach oben scrollen