Algorithmes en JavaScript pour les débutants

Les algorithmes sont les principaux blocs de construction de la programmation. Ils aident à résoudre les problèmes de manière efficace et rapide. Dans cet article, nous examinerons quelques algorithmes populaires en JavaScript et verrons comment ils fonctionnent dans la pratique. Nous discuterons du tri, de la recherche et des principes de base du travail avec les données.

Que sont les algorithmes ?

Un algorithme est une séquence d'étapes qui est exécutée pour atteindre un objectif spécifique ou résoudre un problème. En programmation, nous utilisons des algorithmes pour trier des tableaux, rechercher des valeurs, gérer des données et bien plus encore. Plus l'algorithme est bon, plus il fonctionne rapidement et efficacement.

Commençons par les algorithmes les plus populaires qui sont souvent utilisés en JavaScript.

Algorithme de tri : tri à bulles (Bubble Sort)

Bubble Sort est l'un des algorithmes de tri les plus simples qui parcourt un tableau, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Ce processus est répété jusqu'à ce que le tableau soit trié.

Exemple de code JavaScript :

function bubbleSort(arr) {
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // On change les éléments de place
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
    } while (swapped);
    return arr;
}

// Exemple d'utilisation
const array = [5, 3, 8, 4, 2];
console.log(bubbleSort(array)); // [2, 3, 4, 5, 8]

Comment fonctionne le tri à bulles ? Nous parcourons le tableau et comparons les paires d'éléments. Si l'élément actuel est plus grand que le suivant, nous les échangeons. Après un passage, le plus grand élément « remonte » à la fin du tableau (d'où le nom de « tri à bulles »). Le processus est répété jusqu'à ce que l'ensemble du tableau soit trié.

Algorithme de recherche : Recherche binaire (Binary Search)

La recherche binaire est un algorithme de recherche efficace utilisé pour trouver un élément dans un tableau trié. Contrairement à la recherche linéaire, qui vérifie chaque élément séquentiellement, la recherche binaire divise le tableau en deux parties et compare la valeur recherchée avec le milieu. Cela permet de réduire considérablement le nombre de contrôles.

Exemple de code JavaScript :

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Nous avons trouvé l'élément, nous renvoyons son index
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Élément non trouvé
}

// Exemple d'utilisation
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(sortedArray, 4)); // 3

Comment fonctionne la recherche binaire ? Nous trouvons le milieu du tableau et le comparons à l'élément cible. Si l'élément est inférieur, nous continuons la recherche dans la moitié gauche du tableau, s'il est supérieur, nous continuons la recherche dans la moitié droite. Ce processus est répété jusqu'à ce que nous trouvions l'élément ou que nous soyons sûrs qu'il n'est pas dans le tableau.

Veuillez noter que la recherche binaire ne fonctionne qu'avec des tableaux triés. Si le tableau n'est pas trié, il faut d'abord le trier.

Récursion : algorithme de calcul de la factorielle

Récursivité — c'est quand une fonction s'appelle elle-même pour résoudre un sous-problème. Un exemple classique de récursion est le calcul de la factorielle d'un nombre. La factorielle d'un nombre n est le produit de tous les nombres de 1 à n.

Exemple de code JavaScript :

function factorial(n) {
    if (n === 0) {
        return 1; // La factorielle de 0 est égale à 1
    }
    return n * factorial(n - 1); // Appel de fonction récursif
}

// Exemple d'utilisation
console.log(factorial(5)); // 120

Comment fonctionne la récursion dans la factorielle ? Lorsque factorial(5) est appelé, la fonction s'appelle avec l'argument 5 - 1, puis 4 - 1 et ainsi de suite jusqu'à ce qu'elle atteigne 0. Après cela, le résultat est renvoyé à travers la chaîne d'appels, et nous obtenons le produit de tous les nombres de 1 à 5.

Algorithme de tri : tri rapide (Quick Sort)

Quick Sort — c'est l'un des algorithmes de tri les plus populaires, qui fonctionne beaucoup plus rapidement que le tri par bulle dans la plupart des cas. Il utilise le principe « diviser pour régner », en choisissant un élément de référence et en divisant le tableau en deux parties : moins de référence et plus de référence. Ensuite, les deux parties sont triées de manière récursive.

Exemple de code JavaScript :

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // Cas de base : un tableau d'un élément est déjà trié
    }

    const pivot = arr[arr.length - 1]; // Élément de support
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]); // Les éléments plus petits que l'élément de référence vont dans le tableau de gauche
        } else {
            right.push(arr[i]); // Les éléments plus grands que l'élément de référence vont dans le tableau de droite
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)]; // Appel récursif pour chaque partie
}

// Exemple d'utilisation
const arrayToSort = [5, 3, 8, 4, 2];
console.log(quickSort(arrayToSort)); // [2, 3, 4, 5, 8]

Comment fonctionne le tri rapide ? Nous choisissons l'élément de référence (dans ce cas, le dernier élément du tableau), puis divisons le tableau en deux parties : les éléments plus petits que l'élément de référence et les éléments plus grands que l'élément de référence. Ces parties sont triées de manière récursive jusqu'à ce que les tableaux soient triés.

Conclusion

Les algorithmes sont une partie importante de la programmation, et comprendre leur fonctionnement vous aidera à écrire un code plus efficace. Dans cet article, nous avons examiné plusieurs algorithmes populaires en JavaScript, notamment le tri, la recherche et la récursion. Chacun de ces algorithmes peut être utilisé dans le développement quotidien pour résoudre des problèmes de complexité variable.

Essayez d'appliquer ces algorithmes à vos projets ! L'amélioration de vos compétences en matière d'algorithmes fera de vous un développeur plus avancé et vous aidera à écrire un code optimisé et propre.