Les algorithmes de tri Flashcards
1
Q
Selon quelles propriétés caractérise-t-on les algorithmes de tri ?
A
- Complexité du temps d’exécution
- Utilisation de mémoire pour le tri (in situ ou dans une structure intermédiaire)
- Stabilité (Conserve l’ordre original pour les éléments de clés égales)
2
Q
Principe du tri par insertion
A
- 2 boucles, une de p=1 à n, l’autre de j=p à 1
- Comparer a[j] à a[j-1] et swaper si nécessaire
3
Q
Propriétés du tri par insertion
A
- θ(n^2) en pire cas et θ(n) en meilleur cas
- In situ
- Stable
4
Q
Optimisation du tri par insertion
A
On mémorise tmp = a[j], on décale a[j-1] dans a[j] et on insère tmp quand tmp >= a[j-1]
5
Q
Temps exécution tri fusion
A
θ(n log n) en pire ET meilleur cas
6
Q
Stabilité tri fusion
A
Stable
7
Q
Utilisation mémoire tri fusion
A
θ(n)
8
Q
Temps d’exécution Tri de base
A
θ(n)
9
Q
Utilisation mémoire Tri de base
A
Pas sur place
10
Q
Temps d’exécution AVL
A
θ(n log n) en pire ET meilleur cas
11
Q
Stabilité AVL
A
Peu l’être si on utilise des listes pour stocker les éléments égaux.
12
Q
Utilisation mémoire tri par TAS
A
In situ
13
Q
Utilisation mémoire tri par Arbre
A
Pas sur place
14
Q
Stabilité tri par Tas
A
Pas stable
