Maîtrisez le tri Quicksort pour vos entretiens techniques 🚀

Introduction

Aujourd’hui, j’ai préparé un post un peu spéciale pour vous. Il se trouve que j’ai un ami qui a malheureusement raté son entretien technique parce qu’il n’a pas réussi à implémenter un tri quicksort.

De nos jours, la plupart des langages de haut niveau implémentent déjà ce genre de tri. Mais si vous tombez sur quelqu’un qui est fan d’algorithmie, vous pourriez avoir à en implémenter un durant l’entretien.

Du coup, je vous propose de décortiquer le fonctionnement du tri Quicksort dans cet article, afin de pouvoir assurer lors de vos prochains entretiens.

Comprendre le tri Quicksort

Je vais commencer par vous expliquer, à l’aide d’un diagramme, comment fonctionne le tri Quicksort.

Nous allons voir la version “in place” du Quicksort. Il faut savoir qu’il existe 2 autres versions, mais qui sont un peu plus complexes à mettre en œuvre.

Ce diagramme illustrera le déroulement complet d’un tri Quicksort, depuis un tableau de nombres. Nous allons explorer chaque étape pour voir comment l’algorithme s’exécute.

1ère Itération

La première étape consiste à sélectionner un pivot. Ici, le dernier élément de la liste, le nombre 5, est choisi comme pivot.

Nous allons maintenant diviser le tableau en deux sous-tableaux : l’un contenant les éléments inférieurs au pivot et l’autre avec les éléments supérieurs ou égaux au pivot.

Ensuite, nous parcourons notre tableau initial :

• 7 est plus grand que le pivot, nous le plaçons donc à droite du pivot.
• 1 est plus petit que le pivot, donc nous le plaçons dans le tableau de gauche.
• 10 est plus grand, donc nous le plaçons à droite.
• 8 est aussi plus grand, donc il est placé à droite.

Je pense que vous avez saisi le principe. Il faut répéter cette opération jusqu’à arriver à notre pivot. Une fois arrivé au pivot, nous le plaçons à droite au début du tableau.

Il reste maintenant à répéter la même opération pour les 2 sous-tableaux que nous venons de créer.

2ème Itération

Commençons par la sous-liste de gauche. Nous prenons le dernier élément, à savoir 3, comme pivot.

Ensuite, nous effectuons les mêmes comparaisons qu’auparavant à partir de ce pivot :

• 1 est inférieur à 3, donc il va être placé dans le sous-tableau de gauche.
• 4 est supérieur à 3, donc il va être placé dans le sous-tableau de droite.
• 2 est inférieur au pivot, donc il ira à gauche.

Nous plaçons ensuite le pivot au début du tableau situé à droite. Si nous observons les 2 listes, nos nombres sont désormais bien triés.

Pour la liste de droite, nous répétons le même processus. Maintenant que vous avez compris le principe, je vais accélérer un peu, et cela donne ceci une fois les comparaisons effectuées.

Nous avons obtenu deux sous-listes, et elles ne sont pas encore totalement triées, donc nous allons répéter le processus.

3ème Itération

Pour la liste de gauche, on choisit 6 comme pivot, et nous allons répartir les résultats dans 2 sous-tableaux. Cela donne ceci comme résultat.

Enfin, il reste à faire de même pour la liste de droite, nous prenons 10 comme pivot, et nous répétons les comparaisons.

Et voilà, notre tableau est désormais trié.

Implémentation en Typescript

Passons maintenant à la pratique.

Je commence par définir une fonction quicksort. Cette fonction prendra en entrée un tableau de nombres et retournera un tableau trié.

function quicksort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[arr.length - 1]; // Choix du pivot
    const leftArr = [];
    const rightArr = [];

    for (const el of arr.slice(0, arr.length - 1)) {
        if (el < pivot) {
            leftArr.push(el);
        } else {
            rightArr.push(el);
        }
    }

    // Recursion sur les sous-listes et combinaison des résultats
    return [...quicksort(leftArr), pivot, ...quicksort(rightArr)];
}

console.log(quicksort([2,4,1,3,6,8,10,9,7]));

Cas de base : Si le tableau a une longueur de 1 ou 0, il est déjà trié par définition, donc nous le retournons tel quel.

Choix du pivot : Nous prenons par défaut le dernier élément du tableau.

Initialisation des sous-tableaux : Un pour les éléments inférieurs au pivot et un pour les éléments supérieurs ou égaux au pivot.

Boucle pour diviser les éléments : Nous utilisons une boucle for of avec la méthode slice pour créer une copie du tableau d’origine en retirant le dernier élément. Les éléments sont ensuite triés dans le tableau de gauche ou de droite.

Recursion et combinaison : Nous retournons un tableau combinant le tableau trié à gauche, le pivot, et le tableau trié à droite pour former un tableau trié complet.

Et si j’exécute le script, l’algorithme a correctement trié le tableau. Magnifique !