Fiche de révision : NSI diviser pour régner tri fusion

Qu'est-ce que le tri fusion ?

Un algorithme de tri basé sur le principe de diviser pour régner. Il divise le tableau en sous-tableaux, les trie puis les fusionne.

Vrai ou faux : Le tri fusion est un algorithme in-place.

Faux. Le tri fusion nécessite de l'espace supplémentaire pour stocker les sous-tableaux pendant la fusion.

Définir le principe de diviser pour régner.

C'est une technique algorithmique qui consiste à diviser un problème en sous-problèmes plus simples, à résoudre chaque sous-problème puis à combiner les solutions.

Étapes principales du tri fusion ?

- Diviser le tableau - Trier les sous-tableaux - Fusionner les sous-tableaux triés

Quel est le temps de complexité du tri fusion ?

La complexité temporelle est $\displaystyle O(n imes ext{log} n)$ dans le pire des cas et le meilleur cas.

Complétez : Le tri fusion est efficace pour les grands __________.

tableaux

Comparer tri fusion et tri par insertion.

Le tri fusion est plus rapide pour les grands tableaux, tandis que le tri par insertion est meilleur pour les petits tableaux.

Pourquoi utiliser le tri fusion ?

Il est stable, efficace pour les données volumineuses et possède une complexité prévisible.

Qu'est-ce qu'une fusion dans le tri fusion ?

C'est le processus de combiner deux sous-tableaux triés en un seul tableau trié.

Vrai ou faux : Le tri fusion peut être implémenté de manière récursive.

Vrai. L'algorithme utilise la récursion pour diviser les tableaux.

Exemple de tri fusion : 3, 1, 4, 2.

1. Diviser : [3,1] et [4,2] 2. Trier : [1,3] et [2,4] 3. Fusion : [1,2,3,4]

Quelles sont les caractéristiques du tri fusion ?

- Stable - Non-in-place - Complexité $\displaystyle O(n imes ext{log} n)$

Complétez : Le tri fusion nécessite de l'espace de __________.

stockage supplémentaire

Quels types de données le tri fusion peut-il traiter ?

Il peut traiter tout type de données comparables, y compris les entiers, les chaînes, etc.

Vrai ou faux : Le tri fusion est toujours plus rapide que le tri à bulles.

Vrai. Le tri fusion a une complexité bien meilleure que celle du tri à bulles.

Quels sont les principes du tri fusion ?

1. Diviser le tableau en sous-tableaux. 2. Trier les sous-tableaux de manière récursive. 3. Fusionner les sous-tableaux triés pour former un tableau final trié.

Quelles sont les deux étapes principales du tri fusion ?

1. Diviser : séparer le tableau en sous-tableaux. 2. Fusionner : combiner les sous-tableaux triés.

Étape de division : que fait-on ?

On divise le tableau en deux moitiés jusqu'à obtenir des tableaux de taille 1.

Vrai ou faux : le tri fusion est un algorithme itératif.

Faux. Le tri fusion est un algorithme récursif.

Comment fusionne-t-on deux sous-tableaux ?

On crée un tableau temporaire, puis on compare les éléments des sous-tableaux pour les insérer dans l'ordre.

Qu'est-ce que l'algorithme de fusion ?

C'est un algorithme qui fusionne deux listes triées en une seule liste triée.

Complétez : Pour fusionner, on compare les ___ des sous-tableaux.

éléments

Quelles sont les conditions d'arrêt de la division ?

On arrête lorsque chaque sous-tableau contient un seul élément.

Comparaison : tri fusion vs tri rapide.

Tri fusion : stable, complexe. Tri rapide : instable, plus rapide en moyenne.

Que se passe-t-il lors de la fusion ?

Les éléments sont ajoutés au tableau final dans l'ordre croissant.

Décrivez l'étape de fusion en 3 points.

- Créer un tableau temporaire. - Comparer les éléments. - Insérer dans l'ordre.

Quelles structures de données sont utilisées ?

Tableaux pour stocker les valeurs et listes pour gérer les sous-tableaux.

Vrai ou faux : le tri fusion nécessite plus de mémoire.

Vrai. Il utilise un espace supplémentaire pour le tableau temporaire.

Pourquoi le tri fusion est-il efficace ?

Il divise le problème en plus petits sous-problèmes, ce qui réduit la complexité.

Quel est l'objectif final du tri fusion ?

Obtenir un tableau trié à partir des sous-tableaux fusionnés.

Complexité temporelle du tri fusion ?

$\displaystyle O(n imes ext{log} n)$, où $\displaystyle n$ est le nombre d'éléments à trier.

Complexité spatiale du tri fusion ?

$\displaystyle O(n)$, car l'algorithme nécessite de l'espace additionnel pour les tableaux auxiliaires.

Vrai ou faux : le tri fusion est stable.

Vrai. Le tri fusion conserve l'ordre des éléments égaux.

Comparer tri fusion et tri à bulles.

Tri fusion : $\displaystyle O(n imes ext{log} n)$, efficace sur grands volumes. Tri à bulles : $\displaystyle O(n^2)$, inefficace sur grands volumes.

Formule de la complexité temporelle de l'algorithme ?

$\displaystyle T(n) = 2T(n/2) + O(n)$.

Effet d'un tableau vide sur le tri fusion ?

Le tri fusion retourne un tableau vide. Pas de traitement.

Qu'est-ce qui influence la complexité spatiale ?

La taille des tableaux auxiliaires utilisés lors de la fusion.

Remplissez le blanc : Tri fusion divise __________ tableaux.

le tableau en deux sous-tableaux.

Quelle est la meilleure performance du tri fusion ?

$\displaystyle O(n imes ext{log} n)$, même dans le pire des cas.

Impact de la récursivité sur la complexité ?

La récursivité augmente l'utilisation de la pile, impactant la complexité spatiale.

Vrai ou faux : le tri fusion nécessite un accès séquentiel.

Faux. Il peut accéder aux éléments de manière non séquentielle.

Mieux que tri fusion pour petites listes ?

Le tri par insertion, $\displaystyle O(n^2)$, est souvent plus rapide.

Qu'est-ce qui se passe lors de la fusion ?

Les sous-tableaux triés sont combinés en un seul tableau trié.

Remplissez le blanc : Le tri fusion fonctionne par __________.

diviser et conquérir.