Un voyage à travers les algorithmes utilisant Javascript - Tri par insertion

What is Insertion Sort?

Insertion Sort is another fundamental sorting algorithm in computer science. It builds the final sorted array one item at a time. It's much like sorting a hand of playing cards - you pick up cards one by one and insert each into its proper position among the cards you've already sorted.

How Insertion Sort Works

Insertion Sort iterates through the array, growing the sorted portion with each iteration. For each element, it compares it with the already sorted elements, moving them up until it finds the correct position to insert the current element.

Here's a step-by-step breakdown:

1. Start with the second element (index 1) as the "current" element.
2. Compare the current element with the one before it.
3. If the current element is smaller, compare it with the elements before. Move the greater elements up to make space for the swapped element.
4. Repeat steps 2-3 until the whole array is sorted.

Visualization of Insertion Sort:

Recorded gif from https://visualgo.net/en/sorting

Implementing Insertion Sort in JavaScript

Let's take a look at the implementation of Insertion Sort in JavaScript, with detailed comments explaining each part:

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

Key Points:

1. Two-Directional Process: Insertion Sort operates through a forward-moving outer loop and a backward-looking inner loop, creating a back-and-forth movement that forms the core of the algorithm.
2. Forward Scan (Outer Loop):

   for (let i = 1; i < arr.length; i++)

Moves forward through the array, selecting one unsorted element (currentElement = arr[i]) at a time.

1. Backward Insert (Inner Loop):

   while (j >= 0 && arr[j] > currentElement)

Looks backward into the sorted portion, shifting larger elements right (arr[j + 1] = arr[j]) to make room for the current element.

1. Element Insertion:

   arr[j + 1] = currentElement;

Inserts the current element into its correct position, growing the sorted portion.

1. In-Place and Stable Sorting: Modifies the original array directly, maintaining the relative order of equal elements.

Insertion Sort builds the final sorted array one item at a time, mimicking how you'd sort a hand of cards. It repeatedly selects a card (element) from the unsorted portion and inserts it into its correct position among the sorted cards, shifting larger cards as needed. This intuitive process makes Insertion Sort efficient for small or nearly-sorted datasets.

Is Insertion Sort Stable?

Yes, Insertion Sort is a stable sorting algorithm. Stability in sorting algorithms means that the relative order of equal elements is preserved after sorting. Insertion Sort achieves this naturally due to its method of operation:

1. Preserving Order: When inserting an element into the sorted portion, Insertion Sort only shifts elements that are strictly greater than the current element. This means that if there are multiple elements with the same value, their relative order will be maintained.
2. No Unnecessary Swaps: Unlike some other sorting algorithms that might swap equal elements, Insertion Sort only moves an element when necessary. This characteristic ensures that equal elements remain in their original relative positions.
3. Left-to-Right Processing: By processing the array from left to right and inserting each element into its correct position among the already-sorted elements, Insertion Sort naturally maintains the original order of equal elements.

The stability of Insertion Sort can be particularly useful when sorting complex data structures where maintaining the original order of equal elements is important. For example, when sorting a list of students first by grade and then by name, a stable sort would ensure that students with the same grade remain in alphabetical order by name.

This stability is an inherent property of the basic Insertion Sort algorithm and doesn't require any additional modifications or overhead to achieve, making it a naturally stable sorting method.

Time and Space Complexity Analysis

Insertion Sort's performance characteristics are as follows:

• Time Complexity:

  • Best Case: O(n) - when the array is already sorted
  • Average Case: O(n^2)
  • Worst Case: O(n^2) - when the array is reverse sorted

• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm

Contrairement au tri par sélection, le tri par insertion peut fonctionner correctement sur des tableaux presque triés, atteignant une complexité temporelle proche de la linéaire dans de tels cas.

Avantages et inconvénients du tri par insertion

Avantages :

• Simple à mettre en œuvre et à comprendre
• Efficace pour les ensembles de données de petite à moyenne taille
• Adaptatif - fonctionne bien sur les tableaux presque triés
• Stable - maintient l'ordre relatif des éléments égaux
• Tri sur place (espace O(1))
• Convient aux scénarios de tri en ligne

Inconvénients :

• Inefficace pour les grands ensembles de données (O(n^2) dans les cas moyens et pires)
• Les performances se dégradent rapidement à mesure que la taille d'entrée augmente

Quand utiliser le tri par insertion

• Ensembles de données de petite à moyenne taille (généralement jusqu'à quelques centaines d'éléments)
• Données presque triées
• Scénarios de tri en ligne où les éléments sont reçus et triés progressivement
• En tant que sous-programme dans des algorithmes plus complexes (par exemple, Quicksort pour les petites partitions)

Applications pratiques et cas d'utilisation

1. Implémentations de bibliothèques standard : souvent utilisées pour les petits tableaux ou dans le cadre d'algorithmes de tri hybrides
2. Opérations de base de données : Tri de petits ensembles d'enregistrements
3. Systèmes embarqués : convient aux systèmes aux ressources limitées en raison de sa simplicité et de sa faible surcharge de mémoire
4. Traitement des données en temps réel : maintien de l'ordre trié au fur et à mesure de la réception des données

Conclusion

Le tri par insertion, malgré ses limites pour les grands ensembles de données, offre des avantages précieux dans des scénarios spécifiques. Sa nature intuitive, semblable à la façon dont nous pourrions trier les cartes à la main, en fait un excellent outil pédagogique pour comprendre les algorithmes de tri.

Principaux points à retenir :

• Complexité temporelle optimale de O(n) pour des données presque triées
• Algorithme de tri stable, sur place et adaptatif
• Efficace pour les petits ensembles de données et le tri en ligne
• Souvent intégré aux stratégies de tri hybrides

Bien qu'ils ne soient pas adaptés aux tâches de tri à grande échelle, les principes du tri par insertion sont souvent appliqués dans des méthodes plus sophistiquées. Sa simplicité et son efficacité dans certains scénarios en font un ajout précieux à la boîte à outils algorithmique d'un programmeur.

Le choix de l'algorithme de tri dépend en fin de compte de votre cas d'utilisation spécifique, des caractéristiques des données et des contraintes du système. Comprendre le tri par insertion fournit des informations sur les compromis de conception des algorithmes et jette les bases de l'exploration de techniques de tri plus avancées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!