Den Blasensortierungsalgorithmus verstehen: Eine Schritt-für-Schritt-Anleitung

Bildquelle: mittel

Sortieren ist einer der wichtigsten Teile von Datenstrukturen und Algorithmen. Es gibt viele Arten von Sortieralgorithmen, und hier ist einer der einfachsten Algorithmen: Blasensortierung.

Sortieralgorithmen sind in der Informatik von grundlegender Bedeutung und Bubble Sort ist einer der einfachsten und intuitivsten Sortieralgorithmen. In diesem Beitrag wird untersucht, wie Bubble Sort funktioniert, seine zeitliche Komplexität analysiert und eine JavaScript-Implementierung erläutert.

In dieser Serie werde ich die vollständige Datenstruktur und die Algorithmen des Sortieralgorithmus mit Javascript teilen und mit der Blasensortierung beginnen. Wenn Sie möchten und möchten, dass ich den vollständigen Sortieralgorithmus mit einem Beispiel teile, liken Sie mich bitte und folgen Sie mir. Es motiviert mich, die Inhalte für euch zu erstellen und vorzubereiten.

Was ist Blasensortierung?

Bubble Sort ist ein einfacher Sortieralgorithmus, der wiederholt durch die Liste geht, benachbarte Elemente (nächste Elemente) vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird wiederholt, bis die Liste sortiert ist. Der Algorithmus hat seinen Namen, weil kleinere Elemente an den Anfang der Liste „sprudeln“.

JavaScript-Implementierung:

Lassen Sie uns in den Code eintauchen, um zu sehen, wie Bubble Sort in JavaScript implementiert wird:

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

Ausgabe

Sortieren mit absteigender Reihenfolge:

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

Ausgabe:

Bereits Kommentare hinzugefügt und jede Zeile des obigen Codes erklärt. Aber ich werde es auch im Detail erklären, damit Sie den gesamten Prozess und die Codes besser verstehen.

So funktioniert es:

• Initialisierung: Wir beginnen mit der Bestimmung der Länge des Arrays, was dabei hilft, die Anzahl der Iterationen zu steuern.
• Äußere Schleife: Diese Schleife wird n-1 Mal ausgeführt, wobei n die Länge des Arrays ist. Jede Iteration stellt sicher, dass das nächstgrößere Element an der richtigen Position platziert wird.
• Innere Schleife: Bei jedem Durchgang der äußeren Schleife vergleicht die innere Schleife benachbarte Elemente und tauscht sie aus, wenn sie nicht in der richtigen Reihenfolge sind. Der Bereich der inneren Schleife verringert sich mit jedem Durchgang, da die größten Elemente bereits am Ende des Arrays sortiert sind.
• Austauschen: Wenn ein Element größer als das nächste ist, werden sie mithilfe einer temporären Variablen ausgetauscht.
• Rückgabe: Abschließend wird das sortierte Array zurückgegeben.

Optimierte Version:

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

Erläuterungen:

• für (sei i = 0; i < len — 1; i ) Dies ist die äußere Schleife, die n-1 Mal ausgeführt wird, wobei n die Länge des Arrays ist. Die äußere Schleife steuert, wie oft die innere Schleife ausgeführt wird. Jede Iteration der äußeren Schleife stellt sicher, dass das nächstgrößere Element an der richtigen Position platziert wird.
• sei isSwapped = false Eine boolesche Variable isSwapped wird mit „false“ initialisiert. Diese Variable wird verwendet, um zu verfolgen, ob während des aktuellen Durchlaufs der inneren Schleife Elemente ausgetauscht wurden. Wenn keine Swaps stattfinden, ist das Array bereits sortiert und der Algorithmus kann vorzeitig beendet werden.
• für (sei j = 0; j < len — i — 1; j ) { Dies ist die innere Schleife, die über die Array-Elemente bis zu len - i - 1 iteriert. Der - i-Teil stellt sicher, dass die Schleife die Elemente nicht berücksichtigt, die bereits in vorherigen Durchgängen sortiert wurden.
• if (array[j] > array[j 1]) { Diese Bedingung prüft, ob das aktuelle Element größer als das nächste Element ist. Wenn dies der Fall ist, ist ein Austausch erforderlich, um die Elemente korrekt anzuordnen.

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

• Diese Zeilen führen den Austausch der Elemente array[j] und array[j 1] mithilfe einer temporären Variablen temp durch. Nach dem Austausch wird isSwapped auf true gesetzt, was anzeigt, dass ein Austausch stattgefunden hat.

// optimized version:
function bubble_sort(array) {
    const len = array.length; // get the length of the array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop run n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value
        let isSwapped = false;
        for (let j = 0; j < len - i -1; j++) {
            //check if the first element is greater than the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwapped =  true;
            }
        }

        //If no element swap by inner loop then break;
        if (isSwapped === false) {
            break;
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

• Nach Abschluss der inneren Schleife prüft diese Bedingung, ob isSwapped immer noch falsch ist. Wenn keine Swaps durchgeführt wurden, ist das Array bereits sortiert und die äußere Schleife kann mit break.
vorzeitig verlassen werden
• Schließlich wird das sortierte Array zurückgegeben.

Zeitkomplexität

Die zeitliche Komplexität von Bubble Sort beträgt im schlimmsten und durchschnittlichen Fall (O(n²)), wobei (n) die Anzahl der Elemente im Array ist. Dies liegt daran, dass jedes Element mit jedem anderen Element verglichen wird. Im besten Fall, wenn das Array bereits sortiert ist, kann die zeitliche Komplexität (O(n)) betragen, wenn eine Optimierung hinzugefügt wird, um den Algorithmus zu stoppen, wenn keine Swaps erforderlich sind.

Im besten Fall, wenn das Array bereits sortiert ist, kann der Algorithmus aufgrund der isSwapped-Optimierung vorzeitig beendet werden, was zu einer zeitlichen Komplexität von (O(n)) führt.

Insgesamt ist die Blasensortierung aufgrund ihrer quadratischen Zeitkomplexität für große Datensätze nicht effizient, kann aber für kleine Arrays oder als Lehrmittel zum Verständnis von Sortieralgorithmen nützlich sein.

Abschluss

Bubble Sort ist aufgrund seiner Einfachheit ein hervorragender Algorithmus für Bildungszwecke. Aufgrund seiner quadratischen Zeitkomplexität ist es jedoch nicht für große Datensätze geeignet. Trotz seiner Ineffizienz bietet das Verständnis von Bubble Sort eine Grundlage für das Erlernen fortgeschrittenerer Sortieralgorithmen.

Das obige ist der detaillierte Inhalt vonDen Blasensortierungsalgorithmus verstehen: Eine Schritt-für-Schritt-Anleitung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!