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(n2)), 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!