Algorithmes de tri — 03 — Le tri par fusion, diviser pour régner
Le tri par fusion (merge sort) : découper, trier les moitiés, fusionner. Pourquoi il garantit O(n log n) dans tous les cas, son coût mémoire et sa stabilité.
Articles : algorithmes
21 articles sur le thème "algorithmes".
Complexité algorithmique — 00 — Le code qui marche en dev et meurt en prod
Pourquoi un code rapide sur 100 lignes devient inutilisable sur 1 million. Introduction à la complexité algorithmique comme dette technique qui dort.
Recherche et tableaux — 06 — Reconnaître le bon pattern
Synthèse de la série : un arbre de décision pour choisir entre dichotomie, deux pointeurs, fenêtre glissante et sommes préfixes face à un problème de tableau.
Recherche et tableaux — 02 — Dichotomie avancée : frontières et recherche sur la réponse
Au-delà de la valeur exacte : trouver la borne inférieure/supérieure avec la dichotomie, et la technique de recherche binaire sur l'espace des réponses.
Algorithmes de tri — 01 — Tri par sélection et tri par insertion
Les deux tris quadratiques fondamentaux : sélection et insertion. Principe, code en TypeScript et Python, complexité, stabilité, et pourquoi l'insertion est meilleure.
Algorithmes de tri — 06 — Les tris linéaires : comptage et radix
Battre la barrière O(n log n) : le tri par comptage et le tri radix trient en O(n) sans comparer les éléments. Conditions, principe, code et limites.
Algorithmes de tri — 00 — Pourquoi étudier le tri quand sort() existe déjà
Tous les langages ont un tri intégré. Pourquoi comprendre les algorithmes de tri reste utile : choisir, déboguer, et raisonner sur la complexité.
Algorithmes de tri — 05 — Le tri par tas (heapsort)
Le tri par tas : utiliser un tas binaire pour trier en O(n log n) garanti et en place. Principe du tas, tamisage, et comparaison avec fusion et rapide.
Recherche et tableaux — 05 — Les sommes préfixes
Le pattern des sommes préfixes : précalculer des cumuls pour répondre à des requêtes de somme sur une plage en O(1). Extension en 2D et différence avec la fenêtre.
Recherche et tableaux — 04 — La fenêtre glissante
Le pattern de la fenêtre glissante : résoudre les problèmes de sous-tableaux et sous-chaînes contigus en O(n) au lieu de O(n²), avec fenêtre fixe et variable.
Algorithmes de tri — 02 — Le tri à bulles, à connaître mais pas à utiliser
Le tri à bulles : principe, code, pourquoi il est O(n²), et pourquoi il sert surtout d'exemple pédagogique plutôt que d'outil de production.
Recherche et tableaux — 03 — Le pattern des deux pointeurs
Le pattern des deux pointeurs : résoudre en O(n) des problèmes de paires, de palindromes et de fusion sur des tableaux triés, sans mémoire supplémentaire.
Complexité algorithmique — 01 — La notation Big-O, lue sans maths
Comprendre O(1), O(log n), O(n), O(n log n), O(n²) et O(2ⁿ) avec des exemples de code et une intuition de la vitesse de croissance.
Graphes — 00 — Modéliser un problème en graphe
Introduction aux graphes : sommets et arêtes, vocabulaire (orienté, pondéré, cyclique), et pourquoi voir un problème comme un graphe ouvre des solutions toutes faites.
Graphes — 08 — Les graphes dans le vrai code
Synthèse de la série graphes : reconnaître un problème de graphe dans du code réel (dépendances, réseaux, recommandations) et choisir le bon algorithme.
Recherche et tableaux — 01 — La recherche dichotomique et ses pièges
La recherche dichotomique (binaire) : O(log n) sur un tableau trié. Implémentation correcte, le piège du calcul du milieu, et les erreurs de bornes classiques.
Recherche et tableaux — 00 — Du parcours naïf aux patterns efficaces
Introduction aux techniques de recherche sur tableaux : pourquoi le parcours naïf est souvent un O(n²) évitable, et les patterns qui le remplacent.
Algorithmes de tri — 04 — Le tri rapide (quicksort) et son pire cas
Le tri rapide : pivot, partition, récursion. Pourquoi il est rapide en moyenne (O(n log n)), pourquoi son pire cas est O(n²), et comment choisir un bon pivot.
Complexité algorithmique — 02 — Compter les opérations et ignorer le bruit
Déterminer la complexité d'un code : compter les opérations, garder le terme dominant, ignorer les constantes, et distinguer cas pire, moyen et meilleur.
Algorithmes de tri — 07 — Stabilité, tri en place, et ce que font vraiment sort() et sorted()
Synthèse : stabilité et tri en place, et l'algorithme réel derrière Array.sort() et sorted() — Timsort, un hybride fusion + insertion. Pièges courants du tri.
Structures de données — 00 — Choisir une structure, c'est choisir un profil de coûts
Introduction à la série structures de données : pourquoi chaque structure est un compromis, ce que la série construit, et le lien avec la complexité algorithmique.