Tris et structures de données

#title: "Algorithmes de tri" description: "Comparaison des algorithmes de tri et leurs applications"Copier le lien

#Algorithmes de triCopier le lien

Le tri est l'une des opérations les plus fondamentales en informatique. Comprendre les différents algorithmes de tri et leurs compromis est essentiel pour choisir la meilleure approche selon le contexte.

#Borne inférieure du tri par comparaisonCopier le lien

Théorème : Tout algorithme de tri par comparaison nécessite au minimum comparaisons dans le pire cas.

Démonstration : L'arbre de décision a au moins feuilles. Sa hauteur est donc au moins .

#Algorithmes quadratiquesCopier le lien

#Tri par insertionCopier le lien

L'algorithme maintient une partie triée et insère chaque nouvel élément à sa position.

Complexité :

• Pire cas : (tableau inversé)
• Meilleur cas : (tableau déjà trié)
• Stable et en place

Quand l'utiliser : Petits tableaux (< 20 éléments) ou tableaux presque triés.

#Tri par sélectionCopier le lien

À chaque étape, sélectionne le minimum et l'échange avec la position courante.

Complexité : dans tous les cas.

Avantage : Nombre minimal d'échanges (), utile si les échanges sont coûteux.

#Tri à bullesCopier le lien

Compare et échange les éléments adjacents jusqu'à stabilité.

Complexité :

Intérêt pédagogique uniquement. Rarement utilisé en pratique.

#Algorithmes efficacesCopier le lien

#Tri fusion (Merge Sort)Copier le lien

Principe : Diviser pour régner.

1. Diviser le tableau en deux moitiés
2. Trier récursivement chaque moitié
3. Fusionner les deux moitiés triées

Complexité :

• Temps : dans tous les cas
• Espace : (tableau auxiliaire)

Propriétés : Stable, mais pas en place.

1def merge_sort(arr):2    if len(arr) <= 1:3        return arr4    mid = len(arr) // 25    left = merge_sort(arr[:mid])6    right = merge_sort(arr[mid:])7    return merge(left, right)8 9def merge(left, right):10    result = []11    i = j = 012    while i < len(left) and j < len(right):13        if left[i] <= right[j]:14            result.append(left[i])

#Tri rapide (Quick Sort)Copier le lien

Principe : Choisir un pivot, partitionner, trier récursivement.

Complexité :

• Meilleur/moyen cas :
• Pire cas : (pivot mal choisi)

Optimisations :

• Pivot médian de 3 éléments
• Randomisation du pivot
• Insertion pour les petits sous-tableaux

Propriétés : En place, mais pas stable.

#Tri par tas (Heap Sort)Copier le lien

Utilise une structure de tas pour extraire successivement les maximums.

Complexité :

• Temps : garantie
• Espace : (en place)

Avantage : Combine les avantages du tri fusion (garantie ) et du tri rapide (en place).

#Tris non comparatifsCopier le lien

Ces algorithmes dépassent la borne en exploitant des propriétés spécifiques des données.

#Tri par comptage (Counting Sort)Copier le lien

Pour des entiers dans un intervalle .

Complexité :

#Tri par base (Radix Sort)Copier le lien

Trie chiffre par chiffre, du moins significatif au plus significatif.

Complexité : où = nombre de chiffres.

#Bucket SortCopier le lien

Distribue les éléments dans des seaux, trie chaque seau.

Complexité moyenne : si distribution uniforme.

#Comparaison récapitulativeCopier le lien

#ExercicesCopier le lien

1. Implémentez une version du tri rapide avec pivot randomisé.
2. Montrez que le tri fusion est stable.
3. Comparez expérimentalement les performances sur différentes distributions.