Bubble Sort: Verständnis des einfachsten Sortieralgorithmus

Das Sortieren ist eine grundlegende Operation in der Informatik, und verschiedene Algorithmen wurden entwickelt, um Daten effizient zu organisieren. Ein solcher Algorithmus, der aufgrund seiner Einfachheit oft für Bildungszwecke verwendet wird, ist der Bubble Sort. In diesem Blog-Beitrag werden wir uns mit den inneren Abläufen von Bubble Sort befassen, indem wir den bereitgestellten JavaScript-Code verwenden.

Verständnis des Codes

Lass uns den Code zerlegen, bevor wir die Erklärung vertiefen:

BubbleSort.js


function bubbleSort(arr) {
let i, j;
let len = arr.length;
let isSwapped = false;
    for (i = 0; i < len; i++) {
        isSwapped = false;
        for (j = 0; j < (len - i - 1); j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j]
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSwapped = true;
            }
        }
        if (!isSwapped) {
            break;
        }
    }
    console.log(arr)
}
var arr = [243, 45, 23, 356, 3, 5346, 35, 5];
bubbleSort(arr)

Der Bubble Sort Algorithmus

Bubble Sort ist ein einfacher Sortieralgorithmus, der wiederholt durch die Liste geht, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird so lange wiederholt, bis die Liste sortiert ist. Jetzt gehen wir den Code Schritt für Schritt durch.

1. Äußere Schleife (for i):

Die äußere Schleife durchläuft jedes Element im Array. Die Variable i repräsentiert die Anzahl der Durchläufe durch das Array.

2. Innere Schleife (for j):

Die innere Schleife vergleicht benachbarte Elemente im Array. Die Variable j repräsentiert den aktuellen Index, der betrachtet wird.

3. Vertauschen der Elemente:

Wenn das aktuelle Element größer ist als das nächste Element, werden sie vertauscht. Dieser Vorgang wird fortgesetzt, bis das Ende des Arrays erreicht ist.

4. Überprüfung auf Vertauschungen:

Nach jedem Durchlauf durch das Array wird die Variable isSwapped überprüft. Wenn in einem bestimmten Durchlauf keine Vertauschungen vorgenommen wurden, ist das Array bereits sortiert, und der Sortiervorgang kann beendet werden.

5. Optimierung (!isSwapped):

Diese Optimierung hilft dabei, die Anzahl der Iterationen zu reduzieren, wenn das Array bereits sortiert ist. Wenn in einem Durchlauf keine Vertauschungen stattfinden, bricht der Algorithmus aus der äußeren Schleife aus, da das Array sortiert ist.

6. Ausgabe des sortierten Arrays:

Schließlich wird das sortierte Array auf der Konsole ausgegeben.

Fazit

Bubble Sort ist zwar nicht der effizienteste Sortieralgorithmus für große Datensätze, bietet jedoch eine klare Einführung in das Konzept des Sortierens. Seine Einfachheit und leicht verständliche Logik machen ihn zu einem wertvollen Ausgangspunkt für das Verständnis komplexerer Algorithmen. Wenn Sie die Welt der Sortieralgorithmen erkunden, werden Sie auf verschiedene Ansätze stoßen, die für unterschiedliche Szenarien optimiert sind. Viel Spaß beim Programmieren!