Cet article fait partie d’une série couvrant les algorithmes de tri en JavaScript. Vous pouvez trouver le reste de la série ici. Si vous débutez dans les algorithmes de tri, ou les algorithmes en général, lisez d’abord ceci pour obtenir une base solide pour aller de l’avant. Aujourd’hui, je vais couvrir les tenants et les aboutissants de la sorte d’insertion. Le tri par insertion est plus complexe mais un peu plus utile que le tri par bulles. Le pire des scénarios est similaire à celui du tri à bulles, mais son meilleur cas le rend adapté aux moments où vous êtes à peu près sûr d’une liste presque triée ou probablement déjà triée. Voyons la situation dans son ensemble.
Le tri par insertion fonctionne en examinant chaque élément d’une liste (en commençant par le deuxième élément) et en le comparant à l’élément précédent. Si l’élément précédent est plus grand, ils sont échangés. Cela continue jusqu’à ce que l’élément soit plus petit, puis nous faisons de même pour l’élément suivant de la liste.
Le tri par insertion n’est pas si mauvais.. tant que vous l’utilisez dans les bonnes circonstances.
- Il est plus rapide que la plupart des algorithmes de tri O (n log n) pour les petites listes.
- Il est extrêmement efficace en mémoire et ne nécessite qu’un (1) espace auxiliaire pour le seul élément en cours de déplacement.
- C’est stable — les éléments égaux apparaissent dans le même ordre dans la liste triée.
- Il est adaptatif — il est rapide lors du tri de listes principalement triées ou lors de l’ajout d’éléments à une liste déjà triée.
- C’est très facile à mettre en œuvre!
Complexité
La complexité temporelle de cet algorithme, au pire des cas, est quadratique -O(n2). Lorsque n s’approche de l’infini, le cas moyen s’approche du pire des cas divisé par deux. Cependant, puisque si votre liste est triée ou presque, elle peut être O(n) dans le meilleur des cas et donc bien adaptée à ce scénario.
Quand il est rapide
Comme mentionné ci-dessus, il peut être rapide dans certaines circonstances. Considérez le tableau, lorsque vous utilisez un algorithme comme le tri par fusion, nous aurions toujours besoin de diviser tous les éléments, puis de les fusionner. Avec le tri par insertion, nous avons juste besoin de vérifier que ceux-ci sont dans le bon ordre « trié jusqu’à présent », puis nous les décalons tous d’un index pour 1.
Comme le tri par insertion est un tri adaptatif, il en fait également un « algorithme en ligne », ce qui signifie que nous pouvons commencer à trier avant d’obtenir tous les éléments, puis fusionner les listes une fois le tri partiel terminé.
Pseudocode
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Code
La prochaine ? Fusionner le tri. L’un des algorithmes de tri les plus utilisés aujourd’hui dans les navigateurs.
