Top Algorithmes et structures de données que vous devez vraiment connaître

Si vous voulez devenir ingénieur logiciel, mais que vous ne savez pas par où commencer, épargnons-nous le suspense : ce sont les algorithmes et les structures de données.

Une fois que vous aurez compris l’essentiel de ces piliers de la programmation, vous commencerez à les voir partout. Et plus vous apprendrez d’algorithmes et de structures de données, plus ils serviront de carburant pour votre carrière d’ingénieur logiciel.

Pour commencer, plongeons d’abord dans la recherche et le tri, deux classes d’algorithmes dont vous ne pouvez pas vous passer. Puis faisons un rapide tour d’horizon du reste du paysage qui comprend les arbres, les graphes, la programmation dynamique et des tonnes d’autres choses.

En gros, il y a deux catégories d’algorithmes de recherche que vous devrez connaître tout de suite : linéaire et binaire. La recherche en profondeur (Depth First Search, DFS) et la recherche en largeur (Breadth First Search, BFS) sont également super-importantes, mais nous les garderons pour la section sur la traversée de graphes ci-dessous.

Recherche linéaire

Les algorithmes linéaires et binaires sont nommés ainsi pour décrire combien de temps (complexité temporelle) une recherche va prendre en fonction de la taille de l’entrée qui est recherchée.

Par exemple, avec les algorithmes de recherche linéaire, si vous avez 100 éléments à rechercher, alors le pire scénario nécessiterait que vous regardiez chaque élément de l’entrée avant de tomber sur la valeur souhaitée. On l’appelle linéaire parce que le temps que prend la recherche est exactement corrélé à la quantité d’éléments dans la recherche (100 éléments/entrée =100 vérifications/complexité)

En bref, linéaire = simple (il n’y a rien d’intelligent dans l’algorithme). Par exemple : imaginez que vous essayez de trouver votre ami Lin parmi une file de personnes debout sans ordre particulier. Vous savez déjà à quoi ressemble Lin, il vous suffit donc de regarder chaque personne, une par une, dans l’ordre, jusqu’à ce que vous reconnaissiez ou non Lin. Et c’est tout. Ce faisant, vous suivez l’algorithme de recherche linéaire

Recherche binaire

La recherche binaire tient son nom du fait que le mot binaire signifie  » de ou relatif à 2 choses  » et l’algorithme fonctionne en divisant l’entrée en deux parties jusqu’à ce qu’il trouve l’élément recherché. Une moitié contient l’élément recherché et l’autre moitié ne le contient pas. Le processus se poursuit jusqu’à ce que l’endroit où l’entrée est divisée devienne l’élément recherché. La recherche binaire est en fait une approche très disciplinée du processus d’élimination. Elle est plus rapide que la recherche linéaire, mais elle ne fonctionne qu’avec des séquences ordonnées.

Un exemple devrait rendre cela plus clair. Supposons que vous essayez de trouver votre ami Bin (qui mesure 5’5 ») dans une file unique de personnes qui ont été ordonnées par taille de gauche à droite, du plus petit au plus grand. La file est vraiment très longue et tu n’as pas le temps de la parcourir une à une en comparant la taille de chacun à celle de Bin. Que pouvez-vous faire ?

Entrez dans la recherche binaire. Vous sélectionnez la personne qui se trouve au milieu de la file d’attente et vous mesurez sa taille. Elle mesure 1m70. Vous savez donc tout de suite que cette personne, ainsi que toutes les personnes à sa droite, ne sont pas Bin. Maintenant que vous avez divisé votre problème en deux, vous portez votre attention sur le reste de la file et choisissez à nouveau la personne du milieu. Elle mesure 1m80. Vous pouvez donc exclure cette personne et toutes celles qui se trouvent à sa gauche, ce qui réduit encore le problème de moitié. Et ainsi de suite. Après seulement cinq ou six de ces divisions, vous avez rapidement trouvé Bin en une fraction du temps qu’il vous a fallu pour trouver Lin. Ce faisant, vous avez suivi l’algorithme de recherche binaire.

Tri

L’ordonnancement, autrement appelé tri, de listes d’éléments est l’une des tâches de programmation les plus courantes que vous effectuerez en tant que développeur. Nous examinons ici deux des algorithmes de tri les plus utiles : MergeSort et QuickSort.

MergeSort

Supposons que plutôt que de tomber sur la ligne ordonnée de personnes dans l’exemple ci-dessus, vous devez créer une ligne ordonnée de personnes à partir d’un groupe non ordonné. Vous n’avez pas beaucoup de temps, alors vous imaginez une stratégie pour accélérer les choses.

Vous demandez d’abord au groupe de personnes, qui sont toutes serrées les unes contre les autres, de se diviser en deux. Ensuite, vous demandez à chacun des deux groupes de se diviser à nouveau en deux, et ainsi de suite, jusqu’à ce que vous ayez entièrement affaire à des individus. Vous commencez alors à mettre les individus par deux, et vous demandez au plus grand des deux de chaque paire de se tenir à la droite de l’autre. Assez rapidement, tout le monde est organisé en ces paires ordonnées gauche-droite.

Puis, vous commencez à fusionner les paires ordonnées en groupes ordonnés de quatre ; puis à fusionner les groupes ordonnés de quatre en groupes ordonnés de huit ; et ainsi de suite. Finalement, vous constatez que vous avez une ligne complète de personnes ordonnée en hauteur, comme celle que vous avez rencontrée plus haut. Sans le savoir, vous avez suivi l’algorithme MergeSort pour accomplir votre exploit.

.

QuickSort

QuickSort est un peu trop complexe pour qu’on puisse facilement se le représenter avec des gens, alors rapprochons-nous un peu du code. Pour commencer, imaginons que vous avez une liste non ordonnée, ou tableau, de huit nombres que vous voulez ordonner.

4 2 13 6 15 12 7 9

Vous pourriez utiliser MergeSort, mais vous entendez dire que QuickSort est généralement plus rapide, alors vous décidez de l’essayer. Votre première étape consiste à choisir un nombre dans la liste appelé le pivot. Le choix du bon numéro de pivot fera toute la différence dans la rapidité d’exécution de votre QuickSort, et il existe des formules toutes faites à suivre pour choisir de bons pivots. Mais pour l’instant, restons simples et choisissons le dernier chiffre du tableau pour notre numéro de pivot : 9.

4 2 13 6 15 12 7 9

Pour faciliter le suivi de l’étape suivante, nous allons créer un séparateur au début du tableau et le représenter par le signe dièse.

# 4 2 13 6 15 12 7 9

En nous déplaçant de gauche à droite dans notre tableau, notre objectif est de mettre tout nombre inférieur au pivot (9) à gauche du séparateur, et tout nombre supérieur (ou égal) au pivot à droite du séparateur. Nous commençons par le premier nombre de notre tableau : 4. Pour le déplacer à gauche du séparateur, il suffit de remonter le séparateur d’un élément :

4 # 2 13 6 15 12 7 9

Nous faisons de même avec le nombre suivant : 2.

4 2 # 13 6 15 12 7 9

Mais nous arrivons ensuite à 13, qui est plus grand que le nombre pivot 9 et déjà à droite du séparateur. Nous le laissons donc tranquille. Ensuite, nous arrivons au 6, qui doit aller à gauche du séparateur. Donc d’abord, nous l’échangeons avec le 13 pour le mettre en position :

4 2 # 6 13 15 12 7 9

Puis nous déplaçons le séparateur devant lui :

4 2 6 # 13 15 12 7 9

Vient ensuite le 15, qui est déjà à droite du séparateur, donc nous le laissons tranquille. Ensuite, nous avons le 12. Même chose. Mais le 7, notre dernier chiffre avant d’atteindre le pivot, a besoin du même genre d’aide pour se déplacer que le 6. Nous échangeons donc le 7 avec le 13 pour le mettre en position :

4 2 6 # 7 15 12 13 9

Puis, une fois de plus, nous déplaçons le séparateur en le dépassant :

4 2 6 7 # 15 12 13 9

Enfin, nous arrivons à notre numéro pivot : 9. En suivant la même logique que ci-dessus, nous échangeons 15 avec 9 pour obtenir le nombre pivot là où il doit être :

4 2 6 7 # 9 12 13 15

Puisque tous les nombres à gauche de 9 sont maintenant plus petits que 9, et que tous les nombres à droite de 9 sont plus grands que 9, nous en avons terminé avec notre premier cycle de QuickSort. Ensuite, nous allons traiter chaque ensemble de quatre nombres de part et d’autre du séparateur comme un nouveau tableau auquel appliquer QuickSort. Nous vous épargnons les détails, mais le prochain cycle nous donnera quatre paires de chiffres auxquels nous pourrons facilement appliquer le dernier cycle de QuickSort. Le résultat final sera la liste ordonnée suivante qui nous a pris moins de temps à générer qu’elle ne l’aurait fait avec le plus simple MergeSort:

2 4 6 7 9 12 13 15

Aide-mémoire sur les algorithmes de tri

Voici les algorithmes de tri les plus courants avec quelques recommandations pour savoir quand les utiliser. Intériorisez-les ! Ils sont utilisés partout !

Tri de tas : Lorsque vous n’avez pas besoin d’un tri stable et que vous vous souciez plus des performances dans le pire des cas que des performances dans le cas moyen. Il est garanti d’être O(N log N), et utilise O(1) d’espace auxiliaire, ce qui signifie que vous ne manquerez pas inopinément d’espace de tas ou de pile sur de très grandes entrées.

Introsort : C’est un tri rapide qui passe à un tri de tas après une certaine profondeur de récursion pour contourner le pire cas O(N²) du tri rapide. C’est presque toujours mieux qu’un simple tri rapide, puisque vous obtenez le cas moyen d’un tri rapide, avec des performances garanties O(N log N). Probablement la seule raison d’utiliser un tri de tas au lieu de cela est dans les systèmes sévèrement contraints par la mémoire où O(log N) d’espace de pile est pratiquement significatif.

Tri d’insertion : Lorsque N est garanti comme étant petit, y compris comme cas de base d’un tri rapide ou d’un tri par fusion. Bien que ce soit O(N²), il a une très petite constante et est un tri stable.

Tri à bulles, tri par sélection : Lorsque vous faites quelque chose de rapide et sale et que, pour une raison quelconque, vous ne pouvez pas simplement utiliser l’algorithme de tri de la bibliothèque standard. Le seul avantage que ceux-ci ont sur le tri d’insertion est d’être légèrement plus facile à mettre en œuvre.

Tri rapide : Lorsque vous n’avez pas besoin d’un tri stable et que les performances du cas moyen comptent plus que celles du cas le plus défavorable. Un tri rapide est O(N log N) en moyenne, O(N²) dans le pire des cas. Une bonne implémentation utilise O(log N) de stockage auxiliaire sous forme d’espace de pile pour la récursion.

Tri de fusion : Lorsque vous avez besoin d’un tri stable, O(N log N), c’est à peu près votre seule option. Les seuls inconvénients sont qu’il utilise O(N) d’espace auxiliaire et a une constante légèrement plus grande qu’un tri rapide. Il y a quelques tris de fusion en place, mais AFAIK ils sont tous soit non stables ou pire que O(N log N). Même les tris en place O(N log N) ont une constante tellement plus grande que le simple tri par fusion qu’ils sont plus des curiosités théoriques que des algorithmes utiles.