Fusionner deux séquences triées
Parcourir les deux listes avec un pointeur chacune
Fusionner deux séquences triées est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
L’étape de fusion
Étant donné deux listes triées, combinez-les en une seule liste triée. Cette fusion est au cœur du tri fusion et apparaît partout. 🔗
Deux entrées, un pointeur chacune
Attribuez à chaque liste son propre pointeur, tous deux commençant à l’indice 0. Vous les avancerez ensemble, sans jamais revenir en arrière.
i = 0
j = 0Toujours prendre le plus petit
À chaque étape, comparez les deux premiers éléments. Ajoutez le plus petit au résultat, car il doit venir ensuite dans l’ordre trié.
Avancer le gagnant
Après avoir pris une valeur, advance uniquement le pointeur de la liste dont elle provient. L’autre liste contient toujours son plus petit élément, qui attend d’être traité.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1La boucle principale
Continuez la fusion while tant que les deux listes contiennent encore des éléments. Dès que l’une d’elles est épuisée, la comparaison n’a plus de sens.
while i < len(a) and j < len(b):
# compare and append
passÉpuiser les éléments restants
Lorsqu’une liste est vide, l’autre est déjà triée : utilisez simplement append pour ajouter directement sa partie restante au résultat.
out.extend(a[i:])
out.extend(b[j:])Pourquoi les fins sont gratuites
La partie restante est déjà ordonnée, il n’est donc plus nécessaire de comparer. L’un des deux appels à extend n’ajoute simplement rien.
Complexité totale linéaire
Chaque élément est examiné une seule fois, donc fusionner deux listes de tailles n et m coûte O(n + m) en temps. Il est impossible d’aller plus vite.
Conserver la stabilité
Utiliser <= lorsque les valeurs sont égales conserve les éléments équivalents dans leur ordre d’origine. Cette stabilité est importante lorsque vous transportez des données supplémentaires.
Fusionner aussi à l’envers
Pour fusionner dans une zone de stockage sans espace libre, parcourez plutôt depuis l’arrière en plaçant le plus grand élément en dernier. C’est la même idée, en miroir.
De la fusion au tri
Séparer, trier les moitiés, puis fusionner : cette récursion constitue le tri fusion. La fusion avec deux pointeurs que vous venez d’apprendre en est le moteur central.
Vérification rapide
Vous fusionnez deux listes triées avec un pointeur dans chacune.
Récapitulatif
Parcourez deux listes triées avec un pointeur dans chacune, prenez toujours le plus petit premier élément, puis ajoutez les éléments restants. L’algorithme s’exécute en O(n + m) et constitue le cœur du tri fusion. 🚀
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « Fusionner deux séquences triées » est-elle gratuite ?
Oui — le texte complet de « Fusionner deux séquences triées » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fusionner deux séquences triées » ?
Parcourir les deux listes avec un pointeur chacune Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Fusionner deux séquences triées » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Deux pointeurs sur un tableau trié
- Trouver une paire d’une somme donnée
- Supprimer les doublons sur place
- Fusionner deux séquences triées