Comprendre l'algorithme de tri à bulles : un guide étape par étape

Source de l'image : moyen

Le tri est l'une des parties les plus importantes des structures de données et des algorithmes. Il existe de nombreux types d'algorithmes de tri, et voici l'un des algorithmes les plus simples : le tri à bulles.

Les algorithmes de tri sont fondamentaux en informatique, et Bubble Sort est l'un des algorithmes de tri les plus simples et les plus intuitifs. Cet article explorera le fonctionnement de Bubble Sort, analysera sa complexité temporelle et présentera une implémentation JavaScript.

Dans cette série, je partagerai la structure complète des données et les algorithmes de l'algorithme de tri en utilisant Javascript et commencerai par Bubble Sort. Si vous aimez et souhaitez que je partage l'algorithme de tri complet avec un exemple, aimez-moi et suivez-moi. Cela me motive à créer et préparer le contenu pour vous les gars.

Qu’est-ce que le tri à bulles ?

Bubble Sort est un algorithme de tri simple qui parcourt la liste à plusieurs reprises, compare les éléments adjacents (éléments suivants) et les échange s'ils sont dans le mauvais ordre. Ce processus est répété jusqu'à ce que la liste soit triée. L'algorithme tire son nom du fait que les éléments plus petits « bullent » en haut de la liste.

Implémentation JavaScript :

Plongeons dans le code pour voir comment Bubble Sort est implémenté en JavaScript :

// 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]; 

Sortir

Tri avec les ordres décroissants :

// 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 ]

Sortir:

Déjà ajouté des commentaires et expliqué chaque ligne du code ci-dessus. mais je vais également vous expliquer en détail pour que cela vous aide à comprendre le processus complet et les codes.

Comment ça marche :

• Initialisation : On commence par déterminer la longueur du tableau, ce qui permet de contrôler le nombre d'itérations.
• Boucle externe : cette boucle s'exécute n-1 fois, où n est la longueur du tableau. Chaque itération garantit que l'élément suivant le plus grand est placé dans sa position correcte.
• Boucle interne : pour chaque passage de la boucle externe, la boucle interne compare les éléments adjacents et les échange s'ils sont dans le désordre. La portée de la boucle interne diminue à chaque passage car les éléments les plus gros sont déjà triés à la fin du tableau.
• Échange : Si un élément est supérieur au suivant, ils sont échangés à l'aide d'une variable temporaire.
• Retour : Enfin, le tableau trié est renvoyé.

Version optimisée :

// 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]; 

Explications :

• pour (soit i = 0 ; i < len — 1 ; i ) Il s'agit de la boucle externe, qui s'exécute n-1 fois, où n est la longueur du tableau. La boucle externe contrôle combien de fois la boucle interne s'exécutera. Chaque itération de la boucle externe garantit que l'élément suivant le plus grand est placé dans sa position correcte.
• soit isSwapped = faux Une variable booléenne isSwapped est initialisée à false. Cette variable est utilisée pour savoir si des éléments ont été échangés lors du passage en cours de la boucle interne. Si aucun échange ne se produit, le tableau est déjà trié et l'algorithme peut se terminer plus tôt.
• pour (soit j = 0 ; j < len — i — 1 ; j ) { Il s'agit de la boucle interne, qui parcourt les éléments du tableau jusqu'à len - i - 1. La partie - i garantit que la boucle ne prend pas en compte les éléments qui ont déjà été triés lors des passes précédentes.
• if (tableau[j] > tableau[j 1]) { Cette condition vérifie si l'élément actuel est supérieur à l'élément suivant. Si c'est vrai, un échange est nécessaire pour ordonner correctement les éléments.

// 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 ]

• Ces lignes effectuent l'échange des éléments array[j] et array[j 1] en utilisant une variable temporaire temp. Après l'échange, isSwapped est défini sur true, indiquant qu'un échange a eu lieu.

// 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]; 

• Une fois la boucle interne terminée, cette condition vérifie si isSwapped est toujours faux. Si aucun échange n'a été effectué, le tableau est déjà trié et la boucle externe peut être quittée plus tôt en utilisant break.
• Enfin, le tableau trié est renvoyé.

Complexité temporelle

La complexité temporelle du Bubble Sort est de (O(n²)) dans les pires et moyens cas, où (n) est le nombre d'éléments dans le tableau. En effet, chaque élément est comparé à tous les autres éléments. Dans le meilleur des cas, lorsque le tableau est déjà trié, la complexité temporelle peut être de (O(n)) si une optimisation est ajoutée pour arrêter l'algorithme lorsqu'aucun échange n'est nécessaire.

Dans le meilleur des cas, lorsque le tableau est déjà trié, l'algorithme peut se terminer prématurément en raison de l'optimisation isSwapped, ce qui entraîne une complexité temporelle de (O(n)).

Dans l'ensemble, le tri à bulles n'est pas efficace pour les grands ensembles de données en raison de sa complexité temporelle quadratique, mais il peut être utile pour les petits tableaux ou comme outil pédagogique pour comprendre les algorithmes de tri.

Conclusion

Bubble Sort est un excellent algorithme à des fins éducatives en raison de sa simplicité. Cependant, il ne convient pas aux grands ensembles de données en raison de sa complexité temporelle quadratique. Malgré son inefficacité, comprendre Bubble Sort constitue une base pour apprendre des algorithmes de tri plus avancés.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!