Sortieralgorithmen: Bubble sort

Der Bubble sort Algorithmus ist ein Verfahren zum sortieren von Objekten. Das zugrundeliegende Verfahren ist einfach aufgebaut. Man vergleicht zwei benachbarte Objekte. Ist das linke Objekt größer als das rechte Objekt, so werden beide Objekte vertauscht. Am ende des Bubble sort Algorithmus haben wir eine aufsteigend sortierte Liste voller Objekte.

Wichtig ist allerdings, dass diese Objekte irgendwie miteinander verglichen werden können. Man kann zwei Strings (Zeichenketten) miteinander vergleichen, indem man die Reihenfolge des Alphabetes miteinbezieht. Das bedeutet, dass a kleiner ist als b, da das a vor dem b kommt. Sollten mehrere Buchstaben gleich sein, z.B. aal und aat, dann wird nach dem dritten Buchstaben sortiert, da die ersten beiden aa identisch sind.
Zahlen lassen sich auch problemlos sortieren. Schwieriger wird es mit Datensätzen, wie eine Adresse oder ein Produkt welches mehrere Informationen beinhaltet. In diesem Fall muss man im Vorfeld festlegen wonach sortiert werden soll. Bei einem Produkt könnte es die Produkt-ID sein.

Zum sortieren von Zahlen benötigen wir eine nicht leere Liste von Zahlen sowie zwei Zeiger die auf zwei Indizes referenzieren. Dies ist notwendig damit man diese zwei Zahlen vertauschen kann.

Das Verfahren beginnt mit den Indizes 0 und 1. Diese zwei Indizes werden verglichen. Ist der linke Wert größer als der rechte Wert, so werden beide Zahlen vertauscht. Ansonsten passiert nichts. Dann kommen die Indizes 1 und 2 dran. Dies geht so lange weiter bis wir am ende der Liste angekommen sind, wenn also der letzte Index mit dem vorletzten Index verglichen wird.

Der Vorteil am Bubble sort ist, dass jeder weitere Sortierdurchgang einen Schleifendurchlauf weniger benötigt, da das jeweils letzte Element bereits sortiert ist. Somit spart man sich pro Sortierdurchgang unnötige Schleifendurchläufe.

• Bubble sort (c++)

#include <iostream>

void bubbleSort(){
    const unsigned int SIZE = 10;
    unsigned int list[SIZE] = {56, 81, 3, 17, 35, 11, 8, 3, 17, 34};
    bool changesDone = true;

    for(unsigned int i = 0; i < SIZE && changesDone ; i++){
        changesDone = false;
        for(unsigned int j = 0; j < SIZE - 1 - i; j++){
            // Beide Werte vergleichen und eventuell tauschen
            // Am Ende steht der groesste Wert ganz oben
            if ( list[j] > list[j+1] ){
                unsigned int temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;
                changesDone = true;
            }
        }
    }

    for(unsigned int res = 0; res < SIZE; res++){
        std::cout << list[res] << "\n";
    }
}

int main(){
    bubbleSort();
}

Quelle
https://www.researchgate.net/publication/291262089_Bubble_sort [letzter Zugriff: 29.01.2020, 19:33]