Scribd
Importer
6 vues2 pages

Algorithme de tri par sélection

L'algorithme de tri par sélection fonctionne en sélectionnant l'élément le plus petit à chaque itération et en le plaçant au début de la liste. Bien qu'il soit simple à comprendre et à implémenter, sa complexité est O(n²) dans tous les cas, ce qui le rend inefficace pour de grandes listes comparé à d'autres algorithmes comme QuickSort ou MergeSort. Les avantages incluent l'absence de mémoire supplémentaire, tandis que les inconvénients concernent sa lenteur sur de grandes données.

Transféré par

hamaniwalid10
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
6 vues2 pages

Algorithme de tri par sélection

L'algorithme de tri par sélection fonctionne en sélectionnant l'élément le plus petit à chaque itération et en le plaçant au début de la liste. Bien qu'il soit simple à comprendre et à implémenter, sa complexité est O(n²) dans tous les cas, ce qui le rend inefficace pour de grandes listes comparé à d'autres algorithmes comme QuickSort ou MergeSort. Les avantages incluent l'absence de mémoire supplémentaire, tandis que les inconvénients concernent sa lenteur sur de grandes données.

Transféré par

hamaniwalid10
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithme de Tri

1. Principe de fonctionnement
L'idée principale est de sélectionner l'élément le plus petit à chaque itération et de le placer au
début de la liste.
Étapes de l'algorithme :
1. Parcourir la liste et chercher l’élément le plus petit.
2. L’échanger avec l’élément en première position.
3. Répéter ce processus en ignorant les éléments déjà triés.
4. Continuer jusqu’à ce que toute la liste soit triée.

2. Explication détaillée avec exemple


Prenons une liste :
Exemple : tab = [64, 25, 12, 22, 11]
Itération 1 :
• On cherche le plus petit élément dans [64, 25, 12, 22, 11].
• 11 est le plus petit → on l'échange avec 64.
• Liste après échange :
[11, 25, 12, 22, 64]
Itération 2 :
• On cherche le plus petit élément dans [25, 12, 22, 64].
• 12 est le plus petit → on l'échange avec 25.
• Liste après échange :
[11, 12, 25, 22, 64]
Itération 3 :
• On cherche le plus petit élément dans [25, 22, 64].
• 22 est le plus petit → on l'échange avec 25.
• Liste après échange :
[11, 12, 22, 25, 64]
Itération 4 :
• On cherche le plus petit élément dans [25, 64].
• 25 est le plus petit, donc pas besoin d'échanger.
• Liste finale triée :
[11, 12, 22, 25, 64]

3. Implémentation en Python
Voici le code en Python qui suit ces étapes :

python
CopierModifier
deftri_selection(tab):
n = len(tab)

fori inrange(n - 1): # On boucle jusqu'à l'avant-dernier élémentmin_index = i # On suppose que le


min est à la position i# Chercher le plus petit élément dans le reste du tableauforj inrange(i + 1, n):
iftab[j] < tab[min_index]:
min_index = j # Mise à jour de l'indice du plus petit élément# Échanger tab[i] avec
tab[min_index]tab[i], tab[min_index] = tab[min_index], tab[i]
# Exemple d'utilisationliste = [64, 25, 12, 22, 11]
tri_selection(liste)
print("Liste triée :", liste)
Sortie :

less
CopierModifier
Listetriée: [11, 12, 22, 25, 64]

4. Analyse de la complexité
• Meilleur cas (déjà trié) : O(n²)
• Cas moyen : O(n²)
• Pire cas (ordre inverse) : O(n²)
Le tri par sélection n'est pas un tri efficace comparé à QuickSort (O(n log n)) ou MergeSort (O(n log
n)).
Cependant, il est facile à comprendre et à implémenter.

5. Avantages et Inconvénients
Avantages :
Facile à comprendre et à coder.
Pas besoin de mémoire supplémentaire (tri en place).
Inconvénients :
Lent sur de grandes listes (O(n²)).
Pas adapté aux grandes données.

Vous aimerez peut-être aussi