Un tutoriel pour coder les entretiens

Le classement des ensembles de données est un élément fondamental du traitement dans les applications informatiques.

Cette opération est essentielle pour l'affichage et la recherche de données. Il n'est donc pas étonnant que tout bon développeur maîtrise l'art du tri des tableaux. Cet article détaille certains des algorithmes les plus répandus pour le tri de tableaux en JavaScript.

Qu'est-ce que le tri et en quoi est-il pertinent ?

Source: Unsplash

Le tri consiste à organiser méthodiquement des valeurs selon un ordre défini. Cet ordre peut être soit descendant, soit ascendant. En JavaScript, le tri de tableaux est crucial car il permet une présentation des données plus structurée et plus pertinente.

Par exemple, un utilisateur peut préférer visualiser ses fichiers en commençant par les plus récents ou les produits par ordre de prix. De plus, le tri est un prérequis pour l'application de la recherche binaire, qui ne fonctionne qu'avec des données préalablement ordonnées.

Bien que des fonctions et des bibliothèques facilitent le tri de données, une compréhension des mécanismes sous-jacents reste indispensable pour les entretiens techniques et les situations où un code de bas niveau est requis.

Algorithmes de tri de tableaux en JavaScript

Tri à bulles

Le tri à bulles est probablement l'algorithme le plus simple à saisir et à mettre en œuvre. Il procède par un balayage unique du tableau. Lors de ce balayage, on parcourt le tableau, du début à la fin, en comparant deux éléments adjacents. Si ces éléments sont mal positionnés, on les intervertit.

On réalise n itérations, où n correspond au nombre d'éléments dans le tableau. À chaque itération, le tableau est trié en partant de la droite. Voici le pseudo-code de l'algorithme pour trier des nombres par ordre croissant :

1. Soit n le nombre d'éléments du tableau
2. Effectuer une boucle n fois, en utilisant i comme compteur (et réaliser les actions suivantes dans chaque boucle)
   a. Parcourir le tableau du deuxième élément jusqu'à l'élément (n - i)ème
   b. Si l'élément précédent est supérieur à l'élément actuel, les échanger.

La traduction de ce pseudo-code en JavaScript donne ce qui suit :

function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i++) {
        for (let j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    
    return arr;
}

Pour une meilleure compréhension du fonctionnement, il est recommandé d'ajouter des `console.log` à l'intérieur des deux boucles afin d'observer l'évolution du tableau à chaque passage.

Dans le code ci-dessous, la fonction de tri a été modifiée pour inclure des `console.log` à l'intérieur des boucles. Un petit tableau non trié est également créé et trié à l'aide de la fonction.

function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i++) {
	console.log(`Pass: ${i}`);

        for (let j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
	
	    console.log(arr);
        }
    }
    
    return arr;
}

const array = [9, 2, 7, 4, 1];
sort(array);

console.log(array);

Le résultat de l'exécution du code ci-dessus est le suivant :

Le tri à bulles a une complexité temporelle Big O de O(n^2). En effet, il effectue n passes, qui parcourent le tableau à chaque passe. Il n'est donc pas très performant pour les grands ensembles de données. Toutefois, sa complexité spatiale est de O(1), car il modifie les éléments du tableau en place.

Tri par insertion

Le tri par insertion est un algorithme courant de tri de tableaux en JavaScript. Imaginons que nous utilisions le tri par insertion pour trier les valeurs par ordre croissant. L'algorithme consiste à choisir un élément, que nous appellerons `num`. Puis, nous déplaçons `num` vers la gauche jusqu'à ce que l'élément à sa gauche soit inférieur à `num`. Si cette procédure est appliquée à partir du deuxième élément jusqu'à la fin, tous les éléments seront triés. Voici le pseudo-code de cette opération.

1. Soit n le nombre d'éléments du tableau
2. Parcourir i de 1 à n - 1 (en commençant par le deuxième élément)
    a. Définir currentElement à array[i]
    b. Définir j à i - 1
    c. Tant que j >= 0 et array[j] > current_element
       i. Déplacer array[j] à array[j+1]
       ii. Décrémenter j de 1
    d. Définir array[j+1] à current_element

L'implémentation de ce pseudo-code en JavaScript donne ceci :

function insertionSort(array) {
  const n = array.length;

  for (let i = 1; i < n; i++) {
    const currentElement = array[i];
    let j = i - 1;

    while (j >= 0 && array[j] > currentElement) {
      array[j + 1] = array[j];
      j -= 1;
    }

    array[j + 1] = currentElement;
  }

  return array;
}

Comme pour le tri à bulles, l'ajout de `console.log` permet de visualiser le déroulement. L'extrait de code ci-dessous illustre le tri par insertion en action.

function sort(array) {
    const n = array.length;

    for (let i = 1; i < n; i++) {
        const currentElement = array[i];
        let j = i - 1;
        console.log("Placing element:", currentElement);

        while (j >= 0 && array[j] > currentElement) {
            array[j + 1] = array[j];
            j -= 1;
        }

        array[j + 1] = currentElement;
        console.log("Placed it at position:", j + 1);
        console.log(array);
    }

    return array;
}

const array = [4, 1, 2, 5, 3];
sort(array);

L'exécution de cet extrait de code donne le résultat suivant :

Tri fusion

Alors que le tri par insertion et le tri à bulles ont une complexité temporelle quadratique, le tri fusion affiche une complexité quasi-linéaire, plus précisément O(n * log(n)).

Le tri fusion utilise la stratégie "diviser pour régner". Le tableau est divisé de manière récursive en sous-tableaux jusqu'à ce que chaque sous-tableau contienne un seul élément. Ensuite, ces sous-tableaux sont fusionnés.

La division est une opération récursive pour permettre la reconstitution du tableau à la suite.

Lors de la fusion, les sous-tableaux sont combinés dans l'ordre. La fusion s'effectue comme lors de la combinaison de deux tableaux triés. Le pseudo-code correspondant est présenté ci-dessous :

1. Si la longueur du tableau est inférieure ou égale à 1, retourner le tableau (cas de base)
2. Trouver l'index du milieu:
   a. Définir mid à la partie entière de (longueur du tableau / 2)
3. Diviser le tableau en deux sous-tableaux:
   a. Créer leftArray et y copier la première moitié du tableau (de l'index 0 à mid)
   b. Créer rightArray et y copier la seconde moitié du tableau (de l'index mid+1 à la fin)
4. Appeler récursivement MergeSort sur leftArray
5. Appeler récursivement MergeSort sur rightArray
6. Fusionner les deux sous-tableaux triés:
   a. Créer un tableau vide resultArray
   b. Tant que leftArray et rightArray ne sont pas vides:
      i. Si le premier élément de leftArray est inférieur ou égal au premier élément de rightArray, l'ajouter à resultArray
      ii. Sinon, ajouter le premier élément de rightArray à resultArray
   c. Ajouter tous les éléments restants de leftArray à resultArray (s'il y en a)
   d. Ajouter tous les éléments restants de rightArray à resultArray (s'il y en a)
7. Retourner resultArray

L'implémentation en JavaScript donne le code suivant :

function sort(array) {

	// Cas de base où l'on arrête la subdivision du tableau
	if (array.length == 1) {
		return array;
	}

	// Trouver le point milieu du tableau
	const m = Math.round(array.length / 2);

	// Diviser le tableau en deux moitiés
	const leftUnsorted = array.slice(0, m);
	const rightUnsorted = array.slice(m);

	// Appeler récursivement le tri fusion
	const leftSorted = sort(leftUnsorted);
	const rightSorted = sort(rightUnsorted);

	// Retourner un tableau fusionné et trié
	return merge(leftSorted, rightSorted);
}

function merge(left, right) {
	// Fusionner deux listes triées
	let result = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex += 1;
		} else {
			result.push(right[rightIndex]);
			rightIndex += 1;
		}
	}

	return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

L'exécution du code avec un exemple de tableau devrait fonctionner.

Tri rapide

Comme le tri fusion, le tri rapide repose sur la stratégie "diviser pour régner". L'algorithme choisit un élément pivot. Puis, il déplace tous les éléments supérieurs au pivot vers sa droite et les éléments inférieurs vers sa gauche. Une fois cette opération achevée, le pivot se trouve à sa position finale.

Pour repositionner les éléments autour du pivot, l'algorithme commence par déplacer le pivot à la fin du tableau.

Après le déplacement, on utilise un pointeur pour parcourir le tableau depuis la gauche, en recherchant le premier nombre supérieur au pivot. Simultanément, un autre pointeur parcourt le tableau depuis la droite, à la recherche du premier nombre inférieur au pivot. Une fois ces deux nombres trouvés, on les permute. Cette procédure est répétée jusqu'à ce que le pointeur de gauche dépasse le pointeur de droite.

À l'arrêt, on permute le plus grand des deux derniers nombres intervertis avec le pivot. À ce stade, le pivot est à la bonne position : les nombres inférieurs au pivot sont à gauche, et les nombres supérieurs sont à droite.

Cette procédure est répétée récursivement pour les sous-tableaux à gauche et à droite du pivot, jusqu'à ce qu'il ne reste plus qu'un seul élément dans les sous-tableaux.

Voici le pseudo-code pour un tri rapide :

1. Si lessThanPointer est inférieur à greaterThanPointer:
    a. Choisir un élément pivot dans le tableau
    b. Déplacer les éléments de sorte que les éléments inférieurs soient à gauche et les éléments supérieurs à droite:
    c. Appeler récursivement Quicksort sur leftSubarray
    d. Appeler récursivement Quicksort sur rightSubarray

La conversion en JavaScript donne le code suivant :

function sort(array, low, high) {
    if (low < high) {
        // Choisir l'index du pivot et partitionner le tableau
        const pivotIndex = move(array, low, high);

        // Trier récursivement les sous-tableaux à gauche et à droite du pivot
        sort(array, low, pivotIndex - 1);
        sort(array, pivotIndex + 1, high);
    }
}

function move(array, low, high) {
    // Sélectionner l'élément pivot (dans ce cas, le dernier élément)
    const pivotElement = array[high];

    // Initialiser l'index pour l'élément plus petit
    let i = low - 1;

    for (let j = low; j < high; j++) {
        // Si l'élément actuel est inférieur ou égal au pivot, l'échanger avec l'élément à l'index i+1
        if (array[j] <= pivotElement) {
            i += 1;
            const temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // Échanger l'élément pivot à sa position correcte
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;

    // Retourner l'index de l'élément pivot
    return i + 1;
}

Le tri d'un exemple de tableau avec le tri rapide dans Node.js devrait donner le résultat suivant :

Dans le meilleur des cas, le tri rapide s'exécute avec une complexité temporelle quasi-linéaire. L'utilisation de l'espace dans le tri rapide évolue également de manière logarithmique. Il est donc relativement efficace par rapport aux autres algorithmes de tri de tableaux en JavaScript.

Conseils pour vos entretiens de programmation

❇️ La pratique est essentielle. Elle aide à maîtriser différents algorithmes, mais surtout à affûter les compétences en résolution de problèmes et en pensée informatique. Il est possible de s'entraîner sur des plateformes telles que LeetCode et AlgoExpert.

❇️ Il est conseillé de tenter de résoudre le problème par soi-même dans un premier temps. Au lieu de passer directement à la solution, il faut essayer de trouver une solution par soi-même, car cela contribue au développement des compétences en résolution de problèmes.

❇️ Si un problème prend trop de temps, il vaut mieux consulter la solution. Il est toujours possible d'apprendre la méthode de résolution à partir de la solution. La plupart des plateformes d'apprentissage proposent des solutions. ChatGPT ou Google Bard sont également de bons outils pour l'explication de concepts.

❇️ De plus, il est recommandé de ne pas écrire le code immédiatement ; la meilleure méthode est d'utiliser un tableau blanc pour les solutions et d'y réfléchir avant de rédiger le code. Le pseudo-code est un moyen efficace d'écrire rapidement des idées.

Conclusion

Dans cet article, nous avons abordé les algorithmes de tri les plus couramment utilisés. Toutefois, la quantité d'informations à assimiler peut sembler intimidante au début. C'est pourquoi il est souvent judicieux de diversifier les sources d'apprentissage au lieu de s'en tenir à une seule. Bonne programmation !

Pour approfondir le sujet, il est également intéressant d'explorer la fonction `sorted` en Python.