Article original : Everything you need to know about Insertion Sort algorithm

Par Sanjula Madurapperuma

Introduction

Bonjour ! Je suis Sanjula, et dans ce guide, j'espère vous enseigner un peu sur l'algorithme de tri par insertion, notamment :

  • Qu'est-ce que le tri par insertion ?
  • Pourquoi le tri par insertion est-il important ?
  • Performance du tri par insertion
  • Comment fonctionne le tri par insertion ?
  • Implémentation Java du tri par insertion

Commençons !

Qu'est-ce que le tri par insertion ?

C'est un algorithme de tri simple qui trie un tableau un élément à la fois.

Pourquoi le tri par insertion est-il important ?

Le tri par insertion présente plusieurs avantages, notamment :

  • La simplicité pure de l'algorithme.
  • L'ordre relatif des éléments avec des clés égales ne change pas.
  • La capacité à trier une liste au fur et à mesure de sa réception.
  • Efficace pour les petits ensembles de données, surtout en pratique par rapport à d'autres algorithmes quadratiques — c'est-à-dire O(n²).
  • Il ne nécessite qu'une quantité constante d'espace mémoire supplémentaire — O(1).

Performance du tri par insertion

  • La performance dans le pire des cas du tri par insertion est O(n²) comparaisons et échanges.
  • La performance dans le meilleur des cas est O(n) comparaisons et O(1) échanges.
  • La performance moyenne est O(n²) comparaisons et échanges.

Comment fonctionne le tri par insertion ?

À chaque itération, le tri par insertion compare l'élément actuel avec l'élément suivant et détermine si l'élément actuel est plus grand que celui avec lequel il a été comparé.

Si c'est vrai, alors il laisse l'élément à sa place et passe à l'élément suivant. Si c'est faux, alors il trouve sa position correcte dans le tableau trié et le déplace à cette position en décalant tous les éléments qui sont plus grands dans le tableau trié d'une position vers l'avant.

Implémentation Java du tri par insertion

P.S. — Essayez de l'implémenter vous-même d'abord !

Félicitations !!! Vous avez maintenant acquis les connaissances de base mais essentielles sur le fonctionnement du tri par insertion.

Pour référence ou pour signaler des problèmes concernant le code ci-dessus, utilisez le lien suivant vers le Gist public GitHub lien.

J'espère que cela a été utile. Merci d'avoir lu ! 😊