# Fichier: python_cheats/cheatsheets/trie.txt
# Cheatsheet Algorithmes de Tri Python - Guide Complet


[OK] TRI À BULLES (BUBBLE SORT)

def bubble_sort(arr):
    """
    BUBBLE SORT - Tri à bulles
    
    COMMENT UTILISER:
    result = bubble_sort([64, 34, 25, 12, 22, 11, 90])
    
    POURQUOI CE TRI:
    - Algorithme simple et intuitif
    - Facile à comprendre et implémenter
    - Bon pour l'enseignement des concepts de tri
    
    QUAND UTILISER:
    - Petits tableaux (n < 20)
    - Données presque triées
    - À des fins éducatives
    - Quand la simplicité prime sur la performance
    
    COMPLEXITÉ:
    - Temps: O(n²) moyenne et pire cas, O(n) meilleur cas
    - Espace: O(1) - tri en place
    - Stable: Oui
    
    QUAND NE PAS UTILISER:
    - Grands tableaux (> 100 éléments)
    - Quand la performance est critique
    """
    # Créer une copie pour ne pas modifier l'original
    arr = arr.copy()
    
    # Longueur du tableau
    n = len(arr)
    
    # Parcourir tous les éléments du tableau
    for i in range(n):
        # Flag pour optimiser si tableau déjà trié
        swapped = False
        
        # Derniers i éléments déjà en place
        for j in range(0, n - i - 1):
            # Comparer éléments adjacents
            if arr[j] > arr[j + 1]:
                # Échanger si dans le mauvais ordre
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Si aucun échange, tableau trié
        if not swapped:
            break
    
    return arr


# Exemple d'utilisation
# data = [64, 34, 25, 12, 22, 11, 90]
# sorted_data = bubble_sort(data)
# print(sorted_data)  # [11, 12, 22, 25, 34, 64, 90]



[OK] TRI PAR INSERTION (INSERTION SORT)


def insertion_sort(arr):
    """
    INSERTION SORT - Tri par insertion
    
    COMMENT UTILISER:
    result = insertion_sort([12, 11, 13, 5, 6])
    
    POURQUOI CE TRI:
    - Efficace pour petits tableaux
    - Excellent pour données presque triées
    - Tri en ligne (peut trier au fur et à mesure)
    - Stable et adaptatif
    
    QUAND UTILISER:
    - Petits tableaux (n < 50)
    - Données presque triées
    - Tri en temps réel (streaming)
    - Comme partie d'algorithmes hybrides (TimSort)
    
    COMPLEXITÉ:
    - Temps: O(n²) moyenne/pire, O(n) meilleur cas
    - Espace: O(1) - tri en place
    - Stable: Oui
    
    AVANTAGES:
    - Simple à implémenter
    - Adaptatif (rapide si déjà trié)
    - Faible overhead
    """
    # Créer une copie pour ne pas modifier l'original
    arr = arr.copy()
    
    # Parcourir à partir du 2ème élément
    for i in range(1, len(arr)):
        # Élément à insérer dans la partie triée
        key = arr[i]
        
        # Position précédente
        j = i - 1
        
        # Déplacer éléments plus grands vers la droite
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # Décaler vers la droite
            j -= 1
        
        # Insérer l'élément à sa position
        arr[j + 1] = key
    
    return arr


# Exemple avec suivi des étapes
# data = [12, 11, 13, 5, 6]
# print("Original:", data)
# sorted_data = insertion_sort(data)
# print("Trié:", sorted_data)



[OK] TRI PAR SÉLECTION (SELECTION SORT)


def selection_sort(arr):
    """
    SELECTION SORT - Tri par sélection
    
    COMMENT UTILISER:
    result = selection_sort([64, 25, 12, 22, 11])
    
    POURQUOI CE TRI:
    - Minimise le nombre d'échanges (n-1 maximum)
    - Simple à comprendre
    - Performant sur petites données
    
    QUAND UTILISER:
    - Coût d'écriture élevé (mémoire flash, EEPROM)
    - Petits tableaux
    - Quand on veut minimiser les écritures
    
    COMPLEXITÉ:
    - Temps: O(n²) dans tous les cas
    - Espace: O(1) - tri en place
    - Stable: Non (mais peut être rendu stable)
    
    CARACTÉRISTIQUES:
    - Nombre d'échanges minimal
    - Performance uniforme (pas d'optimisation)
    - Non adaptatif
    """
    # Créer une copie
    arr = arr.copy()
    n = len(arr)
    
    # Parcourir le tableau
    for i in range(n):
        # Trouver le minimum dans le reste du tableau
        min_idx = i
        
        # Chercher le plus petit élément
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Échanger avec la position actuelle
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr


# Exemple
# data = [64, 25, 12, 22, 11]
# result = selection_sort(data)
# print(result)  # [11, 12, 22, 25, 64]



[OK] TRI FUSION (MERGE SORT)


def merge_sort(arr):
    """
    MERGE SORT - Tri fusion
    
    COMMENT UTILISER:
    result = merge_sort([38, 27, 43, 3, 9, 82, 10])
    
    POURQUOI CE TRI:
    - Garantie O(n log n) dans tous les cas
    - Stable (préserve l'ordre relatif)
    - Prévisible et fiable
    - Excellent pour données liées
    
    QUAND UTILISER:
    - Grands tableaux
    - Quand la stabilité est requise
    - Tri externe (fichiers volumineux)
    - Listes chaînées
    - Quand O(n log n) garanti est nécessaire
    
    COMPLEXITÉ:
    - Temps: O(n log n) dans tous les cas
    - Espace: O(n) - nécessite mémoire supplémentaire
    - Stable: Oui
    
    AVANTAGES:
    - Performance prévisible
    - Parallélisable
    - Bon pour tri externe
    """
    # Cas de base: tableau de 0 ou 1 élément
    if len(arr) <= 1:
        return arr
    
    # Diviser le tableau en deux moitiés
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Récursion sur chaque moitié
    left = merge_sort(left)
    right = merge_sort(right)
    
    # Fusionner les deux moitiés triées
    return merge(left, right)


def merge(left, right):
    """Fusionner deux tableaux triés"""
    result = []
    i = j = 0
    
    # Comparer et fusionner
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Ajouter les éléments restants
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


# Exemple
# data = [38, 27, 43, 3, 9, 82, 10]
# sorted_data = merge_sort(data)
# print(sorted_data)



[OK] TRI RAPIDE (QUICK SORT)


def quick_sort(arr):
    """
    QUICK SORT - Tri rapide
    
    COMMENT UTILISER:
    result = quick_sort([10, 7, 8, 9, 1, 5])
    
    POURQUOI CE TRI:
    - Très rapide en pratique
    - Tri en place (peu de mémoire)
    - Cache-friendly
    - Souvent le plus rapide
    
    QUAND UTILISER:
    - Grands tableaux
    - Quand mémoire limitée
    - Performance moyenne importante
    - Tri de primitifs (int, float)
    
    COMPLEXITÉ:
    - Temps: O(n log n) moyenne, O(n²) pire cas
    - Espace: O(log n) pour la récursion
    - Stable: Non
    
    OPTIMISATIONS:
    - Choisir bon pivot (médiane de 3)
    - Insertion sort pour petits sous-tableaux
    - Tail call optimization
    """
    # Cas de base
    if len(arr) <= 1:
        return arr
    
    # Choisir pivot (ici: élément du milieu)
    pivot = arr[len(arr) // 2]
    
    # Partitionner en 3 groupes
    left = [x for x in arr if x < pivot]    # Plus petits
    middle = [x for x in arr if x == pivot]  # Égaux au pivot
    right = [x for x in arr if x > pivot]    # Plus grands
    
    # Récursion et concaténation
    return quick_sort(left) + middle + quick_sort(right)


def quick_sort_inplace(arr, low=0, high=None):
    """Version en place (économise mémoire)"""
    if high is None:
        high = len(arr) - 1
        arr = arr.copy()
    
    if low < high:
        # Partitionner et obtenir position du pivot
        pi = partition(arr, low, high)
        
        # Trier récursivement avant et après le pivot
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)
    
    return arr


def partition(arr, low, high):
    """Partitionner le tableau"""
    pivot = arr[high]  # Pivot = dernier élément
    i = low - 1  # Index du plus petit élément
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # Placer pivot à sa position finale
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# Exemples
# data = [10, 7, 8, 9, 1, 5]
# print(quick_sort(data))
# print(quick_sort_inplace([10, 7, 8, 9, 1, 5]))



[OK] TRI PAR TAS (HEAP SORT)


def heap_sort(arr):
    """
    HEAP SORT - Tri par tas
    
    COMMENT UTILISER:
    result = heap_sort([12, 11, 13, 5, 6, 7])
    
    POURQUOI CE TRI:
    - Garantie O(n log n) pire cas
    - Tri en place
    - Pas de récursion profonde
    - Pas de pire cas O(n²) comme Quick Sort
    
    QUAND UTILISER:
    - Systèmes temps réel (performance garantie)
    - Mémoire limitée
    - Quand Quick Sort trop risqué
    - Besoin de k plus grands éléments
    
    COMPLEXITÉ:
    - Temps: O(n log n) dans tous les cas
    - Espace: O(1) - tri en place
    - Stable: Non
    
    AVANTAGES:
    - Performance garantie
    - En place
    - Utile pour files de priorité
    """
    arr = arr.copy()
    n = len(arr)
    
    # Construire max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extraire éléments un par un
    for i in range(n - 1, 0, -1):
        # Déplacer racine (max) à la fin
        arr[0], arr[i] = arr[i], arr[0]
        
        # Heapify sur le tas réduit
        heapify(arr, i, 0)
    
    return arr


def heapify(arr, n, i):
    """Maintenir propriété de tas"""
    largest = i  # Racine
    left = 2 * i + 1  # Fils gauche
    right = 2 * i + 2  # Fils droit
    
    # Vérifier si fils gauche plus grand
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Vérifier si fils droit plus grand
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # Échanger et continuer heapify si nécessaire
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


# Exemple
# data = [12, 11, 13, 5, 6, 7]
# sorted_data = heap_sort(data)
# print(sorted_data)



[OK] TRI SHELL (SHELL SORT)


def shell_sort(arr):
    """
    SHELL SORT - Tri Shell
    
    COMMENT UTILISER:
    result = shell_sort([12, 34, 54, 2, 3])
    
    POURQUOI CE TRI:
    - Amélioration du tri par insertion
    - Efficace pour tableaux moyens
    - Simple à implémenter
    - Meilleur que O(n²) simples
    
    QUAND UTILISER:
    - Tableaux moyens (100-5000 éléments)
    - Quand Quick/Merge Sort trop complexes
    - Systèmes embarqués (peu de mémoire)
    - Alternative à insertion sort
    
    COMPLEXITÉ:
    - Temps: O(n log² n) à O(n^1.5) selon gap
    - Espace: O(1) - tri en place
    - Stable: Non
    
    CARACTÉRISTIQUES:
    - Adaptatif
    - Faible overhead
    - Code compact
    """
    arr = arr.copy()
    n = len(arr)
    
    # Commencer avec grand gap, puis réduire
    gap = n // 2
    
    while gap > 0:
        # Tri par insertion avec gap
        for i in range(gap, n):
            temp = arr[i]
            j = i
            
            # Déplacer éléments avec gap
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            
            arr[j] = temp
        
        # Réduire le gap
        gap //= 2
    
    return arr


# Exemple
# data = [12, 34, 54, 2, 3]
# result = shell_sort(data)
# print(result)



[OK] TRI PAR COMPTAGE (COUNTING SORT)


def counting_sort(arr):
    """
    COUNTING SORT - Tri par comptage
    
    COMMENT UTILISER:
    result = counting_sort([4, 2, 2, 8, 3, 3, 1])
    
    POURQUOI CE TRI:
    - O(n + k) linéaire si k petit
    - Stable
    - Pas de comparaisons
    - Prévisible
    
    QUAND UTILISER:
    - Entiers dans petite plage
    - Tri de caractères/bytes
    - k (range) pas trop grand
    - Comme base pour Radix Sort
    
    COMPLEXITÉ:
    - Temps: O(n + k) où k = range des valeurs
    - Espace: O(k)
    - Stable: Oui
    
    LIMITATIONS:
    - Uniquement entiers/caractères
    - Inefficace si k >> n
    - Nécessite mémoire proportionnelle à k
    """
    if not arr:
        return arr
    
    # Trouver min et max
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1
    
    # Créer tableau de comptage
    count = [0] * range_size
    output = [0] * len(arr)
    
    # Compter occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Cumuler les compteurs
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    # Construire tableau de sortie (stable)
    for i in range(len(arr) - 1, -1, -1):
        num = arr[i]
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output


# Exemple
# data = [4, 2, 2, 8, 3, 3, 1]
# sorted_data = counting_sort(data)
# print(sorted_data)



[OK] TRI PAR BASE (RADIX SORT)


def radix_sort(arr):
    """
    RADIX SORT - Tri par base
    
    COMMENT UTILISER:
    result = radix_sort([170, 45, 75, 90, 802, 24, 2, 66])
    
    POURQUOI CE TRI:
    - Linéaire O(nk) pour entiers
    - Stable
    - Efficace pour nombres multi-chiffres
    - Pas de comparaisons
    
    QUAND UTILISER:
    - Entiers avec nombre fixe de chiffres
    - Tri de strings de même longueur
    - Grandes quantités de données
    - Quand k (digits) est petit
    
    COMPLEXITÉ:
    - Temps: O(nk) où k = nombre de chiffres
    - Espace: O(n + k)
    - Stable: Oui
    
    APPLICATIONS:
    - Tri de cartes perforées (historique)
    - Tri d'adresses IP
    - Tri de codes postaux
    """
    if not arr:
        return arr
    
    arr = arr.copy()
    max_val = max(arr)
    
    # Trier chiffre par chiffre
    exp = 1  # 10^0, 10^1, 10^2...
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr


def counting_sort_by_digit(arr, exp):
    """Tri par comptage sur un chiffre spécifique"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 10 chiffres (0-9)
    
    # Compter occurrences du chiffre
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # Cumuler
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Construire sortie (stable)
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # Copier dans arr
    for i in range(n):
        arr[i] = output[i]


# Exemple
# data = [170, 45, 75, 90, 802, 24, 2, 66]
# result = radix_sort(data)
# print(result)



[OK] TRI PAR SEAU (BUCKET SORT)


def bucket_sort(arr, num_buckets=10):
    """
    BUCKET SORT - Tri par seau
    
    COMMENT UTILISER:
    result = bucket_sort([0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434])
    
    POURQUOI CE TRI:
    - Efficace pour données uniformément distribuées
    - O(n) si bonnes conditions
    - Parallélisable
    - Flexible
    
    QUAND UTILISER:
    - Données uniformément distribuées
    - Nombres flottants [0, 1)
    - Distribution connue
    - Tri parallèle possible
    
    COMPLEXITÉ:
    - Temps: O(n + k) moyenne, O(n²) pire cas
    - Espace: O(n + k)
    - Stable: Oui (si tri interne stable)
    
    OPTIMAL QUAND:
    - Données uniformes
    - Nombre de seaux approprié
    - Peu de collisions
    """
    if not arr:
        return arr
    
    # Créer seaux vides
    buckets = [[] for _ in range(num_buckets)]
    
    # Trouver min et max pour normaliser
    min_val, max_val = min(arr), max(arr)
    range_val = max_val - min_val
    
    # Répartir dans les seaux
    for num in arr:
        if range_val == 0:
            index = 0
        else:
            # Normaliser et trouver index du seau
            index = int((num - min_val) / range_val * (num_buckets - 1))
        buckets[index].append(num)
    
    # Trier chaque seau (insertion sort)
    for i in range(num_buckets):
        buckets[i] = insertion_sort(buckets[i])
    
    # Concaténer tous les seaux
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result


# Exemple
# data = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
# sorted_data = bucket_sort(data)
# print(sorted_data)



[OK] TRI TIMSORT (PYTHON DEFAULT)


def tim_sort(arr):
    """
    TIMSORT - Tri hybride de Python
    
    COMMENT UTILISER:
    # Utilisé automatiquement par sorted() et list.sort()
    result = sorted([5, 2, 3, 1, 4])
    arr.sort()  # En place
    
    POURQUOI CE TRI:
    - Optimisé pour données réelles
    - Combine Merge Sort + Insertion Sort
    - Exploite les runs (séquences déjà triées)
    - Très performant en pratique
    
    QUAND UTILISER:
    - Déjà utilisé par défaut en Python!
    - Tous les cas généraux
    - Données partiellement triées
    - Production
    
    COMPLEXITÉ:
    - Temps: O(n log n) pire cas, O(n) meilleur cas
    - Espace: O(n)
    - Stable: Oui
    
    CARACTÉRISTIQUES:
    - Adaptatif (profite des runs)
    - Stable
    - Optimisé pour petits tableaux
    """
    # Note: Implémentation simplifiée
    # Python utilise une version C optimisée
    
    MIN_MERGE = 32
    
    def calc_min_run(n):
        """Calculer longueur minimale de run"""
        r = 0
        while n >= MIN_MERGE:
            r |= n & 1
            n >>= 1
        return n + r
    
    def insertion_sort_run(arr, left, right):
        """Insertion sort sur un run"""
        for i in range(left + 1, right + 1):
            key = arr[i]
            j = i - 1
            while j >= left and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key
    
    arr = arr.copy()
    n = len(arr)
    min_run = calc_min_run(n)
    
    # Trier les runs individuels
    for start in range(0, n, min_run):
        end = min(start + min_run - 1, n - 1)
        insertion_sort_run(arr, start, end)
    
    # Fusionner les runs
    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))
            
            if mid < end:
                left = arr[start:mid + 1]
                right = arr[mid + 1:end + 1]
                merged = merge(left, right)
                arr[start:start + len(merged)] = merged
        
        size *= 2
    
    return arr


# Python utilise TimSort par défaut:
# data = [5, 2, 3, 1, 4]
# sorted_data = sorted(data)  # Utilise TimSort
# data.sort()  # En place avec TimSort



[OK] COMPARAISON & RECOMMANDATIONS


"""
GUIDE DE SÉLECTION D'ALGORITHME DE TRI

┌─────────────────────────────────────────────────────────────┐
│ SCÉNARIO                    │ ALGORITHME RECOMMANDÉ          │
├─────────────────────────────────────────────────────────────┤
│ Usage général Python        │ sorted() / .sort() (TimSort)  │
│ Petits tableaux (< 50)      │ Insertion Sort                │
│ Presque trié                │ Insertion Sort / TimSort      │
│ Grands tableaux             │ Merge Sort / Quick Sort       │
│ Mémoire limitée             │ Heap Sort / Quick Sort        │
│ Garantie O(n log n)         │ Merge Sort / Heap Sort        │
│ Stabilité requise           │ Merge Sort / TimSort          │
│ Entiers petite plage        │ Counting Sort                 │
│ Nombres multi-chiffres      │ Radix Sort                    │
│ Distribution uniforme       │ Bucket Sort                   │
│ Temps réel (pire cas)       │ Heap Sort                     │
│ Cache-friendly              │ Quick Sort                    │
│ Parallélisation             │ Merge Sort                    │
│ Enseignement                │ Bubble Sort / Selection Sort  │
└─────────────────────────────────────────────────────────────┘

COMPLEXITÉS COMPARÉES:

Algorithme      │ Moyenne    │ Pire cas   │ Espace │ Stable
────────────────┼────────────┼────────────┼────────┼────────
Bubble Sort     │ O(n²)      │ O(n²)      │ O(1)   │ Oui
Insertion Sort  │ O(n²)      │ O(n²)      │ O(1)   │ Oui
Selection Sort  │ O(n²)      │ O(n²)      │ O(1)   │ Non
Merge Sort      │ O(n log n) │ O(n log n) │ O(n)   │ Oui
Quick Sort      │ O(n log n) │ O(n²)      │ O(log n)│ Non
Heap Sort       │ O(n log n) │ O(n log n) │ O(1)   │ Non
Shell Sort      │ O(n log n) │ O(n²)      │ O(1)   │ Non
Counting Sort   │ O(n + k)   │ O(n + k)   │ O(k)   │ Oui
Radix Sort      │ O(nk)      │ O(nk)      │ O(n+k) │ Oui
Bucket Sort     │ O(n + k)   │ O(n²)      │ O(n)   │ Oui
TimSort         │ O(n log n) │ O(n log n) │ O(n)   │ Oui

RÈGLES D'OR:

[OK] Utiliser sorted()/list.sort() par défaut en Python
[OK] Tris O(n log n) pour production
[OK] Counting/Radix/Bucket pour cas spéciaux
[OK] Insertion Sort pour petits tableaux
[OK] Merge Sort si stabilité nécessaire
[OK] Heap Sort si mémoire limitée
[OK] Quick Sort si performance moyenne critique

[X] Éviter Bubble/Selection pour grands tableaux
[X] Ne pas réinventer la roue (utiliser built-ins)
[X] Attention aux pires cas de Quick Sort
[X] Counting Sort inadapté si large range
"""



[OK] EXEMPLES PRATIQUES


# Trier liste de dictionnaires (stable important)
users = [
    {'name': 'Alice', 'age': 30},
    {'name': 'Bob', 'age': 25},
    {'name': 'Charlie', 'age': 30}
]
sorted_users = sorted(users, key=lambda x: x['age'])
# TimSort préserve l'ordre pour même âge


# Trier en place
data = [3, 1, 4, 1, 5, 9, 2, 6]
data.sort()


# Tri décroissant
data = [3, 1, 4, 1, 5]
sorted_desc = sorted(data, reverse=True)


# Tri par clé personnalisée
words = ['banana', 'pie', 'Washington', 'book']
sorted_words = sorted(words, key=len)  # Par longueur


# Tri stable (ordre préservé pour égalité)
pairs = [(1, 'one'), (2, 'two'), (1, 'uno'), (2, 'dos')]
sorted_pairs = sorted(pairs, key=lambda x: x[0])
# (1, 'one') reste avant (1, 'uno')


# Tri de tuples (lexicographique)
coordinates = [(1, 3), (2, 1), (1, 2)]
sorted_coords = sorted(coordinates)
# [(1, 2), (1, 3), (2, 1)]


# Tri avec functools (clés multiples)
from functools import cmp_to_key

def compare(a, b):
    # Comparer d'abord par longueur, puis alphabétique
    if len(a) != len(b):
        return len(a) - len(b)
    return -1 if a < b else (1 if a > b else 0)

words = ['apple', 'pie', 'cherry', 'a']
sorted_words = sorted(words, key=cmp_to_key(compare))



[OK] TRI COCKTAIL (COCKTAIL SHAKER SORT)


def cocktail_sort(arr):
    """
    COCKTAIL SORT - Tri cocktail (bidirectionnel)
    
    COMMENT UTILISER:
    result = cocktail_sort([5, 1, 4, 2, 8, 0, 2])
    
    POURQUOI CE TRI:
    - Variation de Bubble Sort
    - Trie dans les deux directions
    - Légèrement plus efficace que Bubble Sort
    - Détecte mieux les tableaux triés
    
    QUAND UTILISER:
    - Petits tableaux
    - Alternative à Bubble Sort
    - Données avec "turtles" (petites valeurs à la fin)
    - À des fins éducatives
    
    COMPLEXITÉ:
    - Temps: O(n²) moyenne/pire, O(n) meilleur cas
    - Espace: O(1) - tri en place
    - Stable: Oui
    
    AVANTAGE SUR BUBBLE SORT:
    - Traite les "turtles" plus rapidement
    - Converge plus vite en pratique
    """
    arr = arr.copy()
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while swapped:
        swapped = False
        
        # Parcours de gauche à droite (comme Bubble Sort)
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        # Si aucun échange, terminé
        if not swapped:
            break
        
        # Réduire la fin (dernier élément en place)
        end -= 1
        swapped = False
        
        # Parcours de droite à gauche
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        # Augmenter le début (premier élément en place)
        start += 1
    
    return arr


# Exemple
# data = [5, 1, 4, 2, 8, 0, 2]
# result = cocktail_sort(data)
# print(result)



[OK] TRI PEIGNE (COMB SORT)


def comb_sort(arr):
    """
    COMB SORT - Tri peigne
    
    COMMENT UTILISER:
    result = comb_sort([8, 4, 1, 56, 3, -44, 23, -6, 28, 0])
    
    POURQUOI CE TRI:
    - Amélioration de Bubble Sort
    - Utilise un gap qui rétrécit
    - Élimine les "turtles" efficacement
    - Plus rapide que Bubble Sort
    
    QUAND UTILISER:
    - Alternative à Bubble Sort
    - Tableaux moyens (100-1000 éléments)
    - Implémentation simple nécessaire
    - Meilleure performance que O(n²) simple
    
    COMPLEXITÉ:
    - Temps: O(n²/2^p) où p = nb passes, O(n log n) en pratique
    - Espace: O(1) - tri en place
    - Stable: Non
    
    CARACTÉRISTIQUES:
    - Gap initial = taille / 1.3
    - Gap diminue par facteur 1.3
    - Finit par Bubble Sort (gap=1)
    """
    arr = arr.copy()
    n = len(arr)
    
    # Initialiser gap
    gap = n
    shrink = 1.3  # Facteur de rétrécissement
    swapped = True
    
    while gap > 1 or swapped:
        # Calculer nouveau gap
        gap = int(gap / shrink)
        if gap < 1:
            gap = 1
        
        swapped = False
        
        # Comparer éléments avec gap
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True
    
    return arr


# Exemple
# data = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
# result = comb_sort(data)
# print(result)



[OK] TRI GNOME (GNOME SORT)


def gnome_sort(arr):
    """
    GNOME SORT - Tri gnome
    
    COMMENT UTILISER:
    result = gnome_sort([34, 2, 10, -9])
    
    POURQUOI CE TRI:
    - Très simple à implémenter
    - Similaire à Insertion Sort
    - Code minimal
    - Conceptuellement simple
    
    QUAND UTILISER:
    - Prototypage rapide
    - Code éducatif
    - Très petits tableaux
    - Quand simplicité > performance
    
    COMPLEXITÉ:
    - Temps: O(n²) moyenne/pire, O(n) meilleur cas
    - Espace: O(1) - tri en place
    - Stable: Oui
    
    MÉTAPHORE:
    - Comme un gnome de jardin triant des pots
    - Avance si ordre correct
    - Recule après échange
    """
    arr = arr.copy()
    n = len(arr)
    index = 0
    
    while index < n:
        # Si au début ou ordre correct, avancer
        if index == 0 or arr[index] >= arr[index - 1]:
            index += 1
        else:
            # Échanger et reculer
            arr[index], arr[index - 1] = arr[index - 1], arr[index]
            index -= 1
    
    return arr


# Exemple
# data = [34, 2, 10, -9]
# result = gnome_sort(data)
# print(result)



[OK] TRI BITONIQUE (BITONIC SORT)


def bitonic_sort(arr, ascending=True):
    """
    BITONIC SORT - Tri bitonique
    
    COMMENT UTILISER:
    # Taille doit être puissance de 2
    result = bitonic_sort([3, 7, 4, 8, 6, 2, 1, 5])
    
    POURQUOI CE TRI:
    - Conçu pour parallélisation
    - Réseau de tri fixe
    - Optimal pour GPU/multi-thread
    - Prédictible
    
    QUAND UTILISER:
    - Calcul parallèle (GPU, CUDA)
    - Architectures vectorielles (SIMD)
    - Réseaux de tri matériels
    - Taille = puissance de 2
    
    COMPLEXITÉ:
    - Temps: O(n log² n) séquentiel
    - Parallèle: O(log² n) avec n processeurs
    - Espace: O(log² n) pour récursion
    - Stable: Non
    
    LIMITATION:
    - Taille doit être puissance de 2
    - Pas optimal en séquentiel
    """
    def bitonic_merge(arr, low, cnt, ascending):
        """Fusionner séquence bitonique"""
        if cnt > 1:
            k = cnt // 2
            for i in range(low, low + k):
                # Comparer et échanger si nécessaire
                if (arr[i] > arr[i + k]) == ascending:
                    arr[i], arr[i + k] = arr[i + k], arr[i]
            # Récursion sur les deux moitiés
            bitonic_merge(arr, low, k, ascending)
            bitonic_merge(arr, low + k, k, ascending)
    
    def bitonic_sort_recursive(arr, low, cnt, ascending):
        """Tri bitonique récursif"""
        if cnt > 1:
            k = cnt // 2
            # Trier première moitié croissant
            bitonic_sort_recursive(arr, low, k, not ascending)
            # Trier deuxième moitié décroissant
            bitonic_sort_recursive(arr, low + k, k, ascending)
            # Fusionner séquence bitonique
            bitonic_merge(arr, low, cnt, ascending)
    
    arr = arr.copy()
    n = len(arr)
    
    # Vérifier puissance de 2
    if n & (n - 1) != 0:
        # Ajuster à la prochaine puissance de 2
        import math
        next_power = 2 ** math.ceil(math.log2(n))
        arr.extend([float('inf')] * (next_power - n))
    
    bitonic_sort_recursive(arr, 0, len(arr), ascending)
    
    # Retirer les éléments ajoutés
    return arr[:n]


# Exemple
# data = [3, 7, 4, 8, 6, 2, 1, 5]
# result = bitonic_sort(data)
# print(result)



[OK] TRI PAIR-IMPAIR (ODD-EVEN SORT)


def odd_even_sort(arr):
    """
    ODD-EVEN SORT - Tri pair-impair
    
    COMMENT UTILISER:
    result = odd_even_sort([34, 2, 10, -9, 5])
    
    POURQUOI CE TRI:
    - Variation parallèle de Bubble Sort
    - Facile à paralléliser
    - Phases alternées pair/impair
    - Simple à implémenter
    
    QUAND UTILISER:
    - Processeurs parallèles
    - Architectures SIMD
    - Comparaisons peuvent être parallèles
    - Enseignement du parallélisme
    
    COMPLEXITÉ:
    - Temps: O(n²) séquentiel, O(n) parallèle
    - Espace: O(1) - tri en place
    - Stable: Oui
    
    PRINCIPE:
    - Phase paire: comparer indices (0,1), (2,3)...
    - Phase impaire: comparer indices (1,2), (3,4)...
    - Alterner jusqu'à tri complet
    """
    arr = arr.copy()
    n = len(arr)
    sorted_flag = False
    
    while not sorted_flag:
        sorted_flag = True
        
        # Phase paire (indices pairs avec suivants)
        for i in range(0, n - 1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                sorted_flag = False
        
        # Phase impaire (indices impairs avec suivants)
        for i in range(1, n - 1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                sorted_flag = False
    
    return arr


# Exemple
# data = [34, 2, 10, -9, 5]
# result = odd_even_sort(data)
# print(result)



[OK] TRI CYCLE (CYCLE SORT)


def cycle_sort(arr):
    """
    CYCLE SORT - Tri cycle
    
    COMMENT UTILISER:
    result = cycle_sort([10, 30, 20, 40, 50])
    
    POURQUOI CE TRI:
    - Minimise le nombre d'écritures
    - Optimal pour écritures coûteuses
    - Théoriquement efficace
    - En place
    
    QUAND UTILISER:
    - Mémoire flash (écritures limitées)
    - EEPROM (usure)
    - SSD (minimiser écritures)
    - Écritures coûteuses en temps/énergie
    
    COMPLEXITÉ:
    - Temps: O(n²)
    - Espace: O(1) - tri en place
    - Stable: Non
    - Écritures: O(n) - minimal!
    
    CARACTÉRISTIQUE UNIQUE:
    - Nombre minimal d'écritures en mémoire
    - Chaque élément écrit maximum 2 fois
    """
    arr = arr.copy()
    n = len(arr)
    writes = 0  # Compteur d'écritures
    
    # Parcourir le tableau pour trouver cycles
    for cycle_start in range(n - 1):
        item = arr[cycle_start]
        
        # Trouver position correcte de l'item
        pos = cycle_start
        for i in range(cycle_start + 1, n):
            if arr[i] < item:
                pos += 1
        
        # Si item déjà en place
        if pos == cycle_start:
            continue
        
        # Ignorer les doublons
        while item == arr[pos]:
            pos += 1
        
        # Placer item à sa position
        arr[pos], item = item, arr[pos]
        writes += 1
        
        # Compléter le cycle
        while pos != cycle_start:
            pos = cycle_start
            
            # Trouver position de l'item
            for i in range(cycle_start + 1, n):
                if arr[i] < item:
                    pos += 1
            
            # Ignorer doublons
            while item == arr[pos]:
                pos += 1
            
            # Placer item
            arr[pos], item = item, arr[pos]
            writes += 1
    
    # print(f"Nombre d'écritures: {writes}")
    return arr


# Exemple
# data = [10, 30, 20, 40, 50]
# result = cycle_sort(data)
# print(result)



[OK] TRI PAR FUSION EXTERNE (EXTERNAL MERGE SORT)


def external_merge_sort_simple(input_file, output_file, chunk_size=1000):
    """
    EXTERNAL MERGE SORT - Tri fusion externe (simplifié)
    
    COMMENT UTILISER:
    external_merge_sort_simple('big_data.txt', 'sorted_data.txt')
    
    POURQUOI CE TRI:
    - Pour fichiers trop grands pour la RAM
    - Divise en chunks triables en mémoire
    - Fusionne les chunks triés
    - Seul tri viable pour très gros volumes
    
    QUAND UTILISER:
    - Fichiers > RAM disponible
    - Big Data
    - Bases de données (tri externe)
    - Traitement par batch
    
    COMPLEXITÉ:
    - Temps: O(n log n)
    - I/O: O(n log n) lectures/écritures
    - Espace: O(chunk_size) en RAM
    
    PRINCIPE:
    1. Découper fichier en chunks
    2. Trier chaque chunk en mémoire
    3. Fusionner chunks triés
    """
    import tempfile
    import heapq
    
    # Phase 1: Créer chunks triés
    temp_files = []
    
    with open(input_file, 'r') as f:
        while True:
            # Lire chunk en mémoire
            chunk = []
            for _ in range(chunk_size):
                line = f.readline()
                if not line:
                    break
                chunk.append(int(line.strip()))
            
            if not chunk:
                break
            
            # Trier chunk
            chunk.sort()
            
            # Écrire dans fichier temporaire
            temp_file = tempfile.NamedTemporaryFile(mode='w+', delete=False)
            for num in chunk:
                temp_file.write(f"{num}\n")
            temp_file.seek(0)
            temp_files.append(temp_file)
    
    # Phase 2: Fusionner tous les chunks (k-way merge)
    with open(output_file, 'w') as out:
        # Heap pour merge efficient
        heap = []
        
        # Initialiser heap avec premier élément de chaque fichier
        for i, temp_file in enumerate(temp_files):
            line = temp_file.readline()
            if line:
                heapq.heappush(heap, (int(line.strip()), i))
        
        # Fusionner
        while heap:
            value, file_idx = heapq.heappop(heap)
            out.write(f"{value}\n")
            
            # Lire prochain élément du même fichier
            line = temp_files[file_idx].readline()
            if line:
                heapq.heappush(heap, (int(line.strip()), file_idx))
    
    # Nettoyer fichiers temporaires
    for temp_file in temp_files:
        temp_file.close()
        import os
        os.unlink(temp_file.name)


# Exemple d'utilisation
# # Créer fichier de test
# with open('big_data.txt', 'w') as f:
#     import random
#     for _ in range(10000):
#         f.write(f"{random.randint(1, 1000000)}\n")
# 
# # Trier
# external_merge_sort_simple('big_data.txt', 'sorted_data.txt', chunk_size=1000)



[OK] TRI INTROSORT (INTRO SORT)


def intro_sort(arr):
    """
    INTROSORT - Tri introspectif (hybride)
    
    COMMENT UTILISER:
    result = intro_sort([7, 2, 1, 6, 8, 5, 3, 4])
    
    POURQUOI CE TRI:
    - Combine Quick Sort + Heap Sort + Insertion Sort
    - Évite pire cas O(n²) de Quick Sort
    - Utilisé en C++ STL (std::sort)
    - Optimal en pratique
    
    QUAND UTILISER:
    - Bibliothèques standard
    - Production (performance garantie)
    - Quand Quick Sort risqué
    - Alternative à TimSort
    
    COMPLEXITÉ:
    - Temps: O(n log n) garanti
    - Espace: O(log n)
    - Stable: Non
    
    STRATÉGIE:
    - Commence avec Quick Sort
    - Bascule vers Heap Sort si récursion trop profonde
    - Utilise Insertion Sort pour petits sous-tableaux
    """
    import math
    
    def intro_sort_helper(arr, start, end, max_depth):
        """Fonction récursive"""
        n = end - start + 1
        
        # Petits tableaux: Insertion Sort
        if n <= 16:
            insertion_sort_range(arr, start, end)
            return
        
        # Récursion trop profonde: Heap Sort
        if max_depth == 0:
            heap_sort_range(arr, start, end)
            return
        
        # Quick Sort normal
        pivot = partition_intro(arr, start, end)
        intro_sort_helper(arr, start, pivot - 1, max_depth - 1)
        intro_sort_helper(arr, pivot + 1, end, max_depth - 1)
    
    def partition_intro(arr, low, high):
        """Partitionnement pour Quick Sort"""
        # Médiane de 3 (début, milieu, fin)
        mid = (low + high) // 2
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[low] > arr[high]:
            arr[low], arr[high] = arr[high], arr[low]
        if arr[mid] > arr[high]:
            arr[mid], arr[high] = arr[high], arr[mid]
        
        pivot = arr[mid]
        arr[mid], arr[high] = arr[high], arr[mid]
        
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    
    def insertion_sort_range(arr, start, end):
        """Insertion sort sur un range"""
        for i in range(start + 1, end + 1):
            key = arr[i]
            j = i - 1
            while j >= start and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key
    
    def heap_sort_range(arr, start, end):
        """Heap sort sur un range"""
        def heapify_range(arr, n, i, start):
            largest = i
            left = 2 * (i - start) + 1 + start
            right = 2 * (i - start) + 2 + start
            
            if left <= n and arr[left] > arr[largest]:
                largest = left
            if right <= n and arr[right] > arr[largest]:
                largest = right
            
            if largest != i:
                arr[i], arr[largest] = arr[largest], arr[i]
                heapify_range(arr, n, largest, start)
        
        # Build heap
        for i in range((end + start) // 2, start - 1, -1):
            heapify_range(arr, end, i, start)
        
        # Extract elements
        for i in range(end, start, -1):
            arr[start], arr[i] = arr[i], arr[start]
            heapify_range(arr, i - 1, start, start)
    
    arr = arr.copy()
    n = len(arr)
    max_depth = 2 * math.floor(math.log2(n))
    intro_sort_helper(arr, 0, n - 1, max_depth)
    return arr


# Exemple
# data = [7, 2, 1, 6, 8, 5, 3, 4]
# result = intro_sort(data)
# print(result)



[OK] TRI BOGO (BOGO SORT) - NE PAS UTILISER!


def bogo_sort(arr, max_iterations=10000):
    """
    BOGO SORT - Tri stupide (aléatoire)
    
    COMMENT UTILISER:
    # NE PAS UTILISER EN PRODUCTION!
    result = bogo_sort([3, 2, 1], max_iterations=100)
    
    POURQUOI CE TRI:
    - Algorithme humoristique
    - Démontre l'inefficacité
    - Enseignement: "comment NE PAS trier"
    - Comparaison avec vrais algos
    
    QUAND UTILISER:
    - JAMAIS en production
    - Humour/démonstration
    - Enseignement (contre-exemple)
    - Tests de patience
    
    COMPLEXITÉ:
    - Temps: O((n+1)!) moyenne, O(∞) pire cas
    - Espace: O(1)
    - Stable: Non
    - Probabilité: 1/n! de réussir par essai
    
    AVERTISSEMENT:
    Pour n=10: ~3.6 millions de permutations
    Pour n=13: ~6 milliards de permutations
    """
    import random
    
    def is_sorted(arr):
        """Vérifier si tableau trié"""
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                return False
        return True
    
    arr = arr.copy()
    iterations = 0
    
    while not is_sorted(arr) and iterations < max_iterations:
        # Mélanger aléatoirement
        random.shuffle(arr)
        iterations += 1
    
    if iterations >= max_iterations:
        print(f"[ATTENTION] Limite atteinte ({max_iterations} essais)")
        return sorted(arr)  # Tricher pour finir
    
    # print(f"[OK] Trié en {iterations} essais")
    return arr


# Exemple (TRÈS petits tableaux uniquement)
# data = [3, 2, 1]
# result = bogo_sort(data, max_iterations=1000)
# print(result)



[OK] BENCHMARKING & TESTS


def benchmark_sorting_algorithms(size=1000, tests=10):
    """
    Comparer performance des algorithmes de tri
    
    COMMENT UTILISER:
    benchmark_sorting_algorithms(size=1000, tests=10)
    
    RÉSULTATS TYPIQUES (1000 éléments):
    - TimSort (Python built-in): ~0.1 ms
    - Quick Sort: ~0.5 ms
    - Merge Sort: ~0.8 ms
    - Heap Sort: ~1.2 ms
    - Shell Sort: ~2 ms
    - Insertion Sort: ~25 ms
    - Bubble Sort: ~50 ms
    """
    import random
    import time
    
    # Algorithmes à tester
    algorithms = {
        'Python sorted()': lambda arr: sorted(arr),
        'Quick Sort': quick_sort,
        'Merge Sort': merge_sort,
        'Heap Sort': heap_sort,
        'Shell Sort': shell_sort,
        'Insertion Sort': insertion_sort,
        'Bubble Sort': bubble_sort,
    }
    
    results = {}
    
    for name, algo in algorithms.items():
        times = []
        
        for _ in range(tests):
            # Générer données aléatoires
            data = [random.randint(1, 10000) for _ in range(size)]
            
            # Mesurer temps
            start = time.perf_counter()
            algo(data)
            end = time.perf_counter()
            
            times.append(end - start)
        
        # Moyenne
        avg_time = sum(times) / len(times)
        results[name] = avg_time
    
    # Afficher résultats
    print(f"\n[GRAPHIQUE] BENCHMARK ({size} éléments, {tests} tests)")
    print("=" * 50)
    
    sorted_results = sorted(results.items(), key=lambda x: x[1])
    for name, time_taken in sorted_results:
        print(f"{name:20s}: {time_taken*1000:8.3f} ms")
    
    return results


# Exemple
# benchmark_sorting_algorithms(size=1000, tests=10)



[OK] TESTS DE VALIDATION


def test_sorting_algorithms():
    """
    Tester tous les algorithmes de tri
    
    COMMENT UTILISER:
    test_sorting_algorithms()
    
    Vérifie:
    - Tri correct
    - Gestion des cas limites
    - Stabilité (quand applicable)
    """
    import random
    
    # Algorithmes à tester
    algorithms = {
        'Bubble Sort': bubble_sort,
        'Insertion Sort': insertion_sort,
        'Selection Sort': selection_sort,
        'Merge Sort': merge_sort,
        'Quick Sort': quick_sort,
        'Heap Sort': heap_sort,
        'Shell Sort': shell_sort,
        'Counting Sort': counting_sort,
        'Radix Sort': radix_sort,
        'Bucket Sort': bucket_sort,
        'Cocktail Sort': cocktail_sort,
        'Comb Sort': comb_sort,
        'Gnome Sort': gnome_sort,
        'Cycle Sort': cycle_sort,
        'Tim Sort': tim_sort,
        'Intro Sort': intro_sort,
    }
    
    test_cases = [
        # Cas normaux
        ([5, 2, 8, 1, 9], [1, 2, 5, 8, 9]),
        ([3, 1, 4, 1, 5, 9, 2, 6], [1, 1, 2, 3, 4, 5, 6, 9]),
        
        # Cas limites
        ([], []),  # Vide
        ([1], [1]),  # Un élément
        ([2, 1], [1, 2]),  # Deux éléments
        
        # Déjà trié
        ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
        
        # Inversement trié
        ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
        
        # Doublons
        ([5, 2, 5, 2, 5], [2, 2, 5, 5, 5]),
        
        # Négatifs
        ([-5, 3, -1, 7, -9], [-9, -5, -1, 3, 7]),
    ]
    
    print("\n[TEST] TESTS DES ALGORITHMES DE TRI")
    print("=" * 60)
    
    for name, algo in algorithms.items():
        passed = 0
        failed = 0
        
        for input_arr, expected in test_cases:
            try:
                # Cas spéciaux pour certains algos
                if name in ['Counting Sort', 'Radix Sort', 'Bucket Sort']:
                    # Ces algos peuvent avoir des limitations
                    if any(x < 0 for x in input_arr):
                        continue  # Skip négatifs pour certains
                
                result = algo(input_arr.copy())
                
                if result == expected:
                    passed += 1
                else:
                    failed += 1
                    print(f"[X] {name} FAILED:")
                    print(f"   Input: {input_arr}")
                    print(f"   Expected: {expected}")
                    print(f"   Got: {result}")
            
            except Exception as e:
                failed += 1
                print(f"[X] {name} ERROR: {e}")
        
        status = "[OK]" if failed == 0 else "[ATTENTION]"
        print(f"{status} {name:20s}: {passed} passed, {failed} failed")
    
    print("=" * 60)


# Exemple
# test_sorting_algorithms()



[OK] VISUALISATION DES TRIS


def visualize_sorting_steps(arr, algorithm_name='bubble_sort'):
    """
    Visualiser étapes d'un algorithme de tri
    
    COMMENT UTILISER:
    visualize_sorting_steps([5, 2, 8, 1, 9], 'bubble_sort')
    
    Affiche chaque étape du tri pour comprendre le fonctionnement
    """
    def bubble_sort_visual(arr):
        """Bubble Sort avec affichage des étapes"""
        arr = arr.copy()
        n = len(arr)
        step = 0
        
        print(f"\n[TELEVISION] VISUALISATION: Bubble Sort")
        print(f"Initial: {arr}")
        print("-" * 40)
        
        for i in range(n):
            swapped = False
            for j in range(0, n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    swapped = True
                    step += 1
                    print(f"Étape {step}: {arr} (échangé {arr[j+1]}<->{arr[j]})")
            
            if not swapped:
                break
        
        print("-" * 40)
        print(f"Final: {arr}")
        return arr
    
    def insertion_sort_visual(arr):
        """Insertion Sort avec affichage des étapes"""
        arr = arr.copy()
        print(f"\n[TELEVISION] VISUALISATION: Insertion Sort")
        print(f"Initial: {arr}")
        print("-" * 40)
        
        for i in range(1, len(arr)):
            key = arr[i]
            j = i - 1
            
            print(f"Insérer {key} dans partie triée: {arr[:i]}")
            
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            
            arr[j + 1] = key
            print(f"Résultat: {arr}")
            print()
        
        print("-" * 40)
        print(f"Final: {arr}")
        return arr
    
    # Sélectionner algorithme
    if algorithm_name == 'bubble_sort':
        return bubble_sort_visual(arr)
    elif algorithm_name == 'insertion_sort':
        return insertion_sort_visual(arr)
    else:
        print(f"Visualisation non disponible pour {algorithm_name}")
        return arr


# Exemple
# visualize_sorting_steps([5, 2, 8, 1, 9], 'bubble_sort')
# visualize_sorting_steps([5, 2, 8, 1, 9], 'insertion_sort')



[OK] UTILITAIRES & HELPERS


def is_sorted(arr, ascending=True):
    """
    Vérifier si tableau est trié
    
    COMMENT UTILISER:
    is_sorted([1, 2, 3, 4, 5])  # True
    is_sorted([5, 4, 3, 2, 1], ascending=False)  # True
    """
    if len(arr) <= 1:
        return True
    
    if ascending:
        return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))
    else:
        return all(arr[i] >= arr[i + 1] for i in range(len(arr) - 1))


def generate_test_data(size, data_type='random'):
    """
    Générer données de test
    
    COMMENT UTILISER:
    random_data = generate_test_data(100, 'random')
    sorted_data = generate_test_data(100, 'sorted')
    reverse_data = generate_test_data(100, 'reverse')
    
    TYPES DISPONIBLES:
    - 'random': Données aléatoires
    - 'sorted': Déjà trié
    - 'reverse': Inversement trié
    - 'nearly_sorted': Presque trié (90% trié)
    - 'duplicates': Beaucoup de doublons
    - 'uniform': Valeurs uniformes
    """
    import random
    
    if data_type == 'random':
        return [random.randint(1, size * 10) for _ in range(size)]
    
    elif data_type == 'sorted':
        return list(range(size))
    
    elif data_type == 'reverse':
        return list(range(size, 0, -1))
    
    elif data_type == 'nearly_sorted':
        arr = list(range(size))
        # Échanger 10% des éléments
        for _ in range(size // 10):
            i, j = random.randint(0, size-1), random.randint(0, size-1)
            arr[i], arr[j] = arr[j], arr[i]
        return arr
    
    elif data_type == 'duplicates':
        # 10 valeurs uniques répétées
        return [random.randint(1, 10) for _ in range(size)]
    
    elif data_type == 'uniform':
        # Toutes les mêmes valeurs
        return [42] * size
    
    else:
        raise ValueError(f"Type '{data_type}' non reconnu")


def compare_stability(arr, sort_func):
    """
    Tester la stabilité d'un tri
    
    COMMENT UTILISER:
    compare_stability([(1, 'a'), (2, 'b'), (1, 'c')], merge_sort)
    
    Un tri est stable si éléments égaux gardent leur ordre relatif
    """
    # Créer tuples avec index original
    indexed_arr = [(val, idx) for idx, val in enumerate(arr)]
    
    # Trier
    sorted_arr = sort_func(indexed_arr)
    
    # Vérifier stabilité
    is_stable = True
    for i in range(len(sorted_arr) - 1):
        if sorted_arr[i][0] == sorted_arr[i + 1][0]:
            if sorted_arr[i][1] > sorted_arr[i + 1][1]:
                is_stable = False
                break
    
    return is_stable


# Exemples
# print(is_sorted([1, 2, 3, 4, 5]))  # True
# data = generate_test_data(100, 'nearly_sorted')
# print(data[:10])



[OK] CAS D'USAGE PRATIQUES


"""
[OBJECTIF] SCÉNARIOS RÉELS ET RECOMMANDATIONS

═══════════════════════════════════════════════════════════════

1⃣ APPLICATION WEB - Tri de résultats de recherche
   [PACKAGE] Données: 100-10000 éléments
   [OBJECTIF] Recommandation: sorted() de Python (TimSort)
   [OK] Raison: Stable, rapide, optimisé
   
   data = [{'name': 'Alice', 'score': 95}, ...]
   sorted_data = sorted(data, key=lambda x: x['score'], reverse=True)


2⃣ SYSTÈMES EMBARQUÉS - Microcontrôleur
   [PACKAGE] Données: 10-100 éléments
   [SAUVEGARDE] Mémoire: Très limitée
   [OBJECTIF] Recommandation: Insertion Sort ou Shell Sort
   [OK] Raison: En place, simple, peu de mémoire
   
   sensors = [temp1, temp2, ...]
   sorted_sensors = insertion_sort(sensors)


3⃣ BASE DE DONNÉES - Tri externe
   [PACKAGE] Données: Millions-milliards d'enregistrements
   [SAUVEGARDE] Mémoire: Données > RAM
   [OBJECTIF] Recommandation: External Merge Sort
   [OK] Raison: Fonctionne avec fichiers volumineux
   
   external_merge_sort_simple('huge_data.db', 'sorted.db')


4⃣ CALCUL SCIENTIFIQUE - NumPy arrays
   [PACKAGE] Données: Millions d'éléments numériques
   [OBJECTIF] Recommandation: numpy.sort() ou numpy.argsort()
   [OK] Raison: Optimisé C, vectorisé, très rapide
   
   import numpy as np
   arr = np.array([3, 1, 4, 1, 5, 9])
   sorted_arr = np.sort(arr)  # QuickSort/MergeSort optimisé


5⃣ GAMING - Leaderboard en temps réel
   [PACKAGE] Données: 1000-100000 joueurs
   [RAPIDE] Contrainte: Temps réel, updates fréquents
   [OBJECTIF] Recommandation: Heap (Priority Queue)
   [OK] Raison: Insertions O(log n), top K efficace
   
   import heapq
   leaderboard = []
   heapq.heappush(leaderboard, (-score, player))
   top10 = heapq.nsmallest(10, leaderboard)


6⃣ COMPTAGE - Âges, notes, votes
   [PACKAGE] Données: Entiers dans petite plage [0-100]
   [OBJECTIF] Recommandation: Counting Sort
   [OK] Raison: O(n) linéaire, parfait pour range limité
   
   ages = [25, 30, 25, 40, 30, 25]  # 0-120 ans
   sorted_ages = counting_sort(ages)


7⃣ TRAITEMENT D'IMAGES - Pixels
   [PACKAGE] Données: Millions de pixels (0-255)
   [OBJECTIF] Recommandation: Radix Sort ou Counting Sort
   [OK] Raison: Valeurs limitées, très rapide
   
   pixels = [120, 45, 200, 67, ...]  # RGB 0-255
   sorted_pixels = radix_sort(pixels)


8⃣ RÉSEAU - Tri de paquets IP
   [PACKAGE] Données: 1000-10000 paquets/seconde
   [RAPIDE] Contrainte: Latence minimale
   [OBJECTIF] Recommandation: Insertion Sort ou Priority Queue
   [OK] Raison: Online algorithm, traitement au fil de l'eau
   
   packets = []
   for packet in stream:
       # Insertion en position triée
       bisect.insort(packets, packet, key=lambda p: p.timestamp)


9⃣ FINANCE - Tri de transactions
   [PACKAGE] Données: 10000-1000000 transactions
   [VERROUILLE] Contrainte: Ordre chronologique préservé (stable)
   [OBJECTIF] Recommandation: Merge Sort ou TimSort
   [OK] Raison: Stable, prévisible O(n log n)
   
   transactions = [{'amount': 100, 'time': t1}, ...]
   sorted_tx = sorted(transactions, key=lambda x: x['amount'])


[10] GPU/PARALLÈLE - Deep Learning
   [PACKAGE] Données: Millions d'éléments
   [ECRAN] Hardware: GPU, multi-core
   [OBJECTIF] Recommandation: Bitonic Sort ou Odd-Even Sort
   [OK] Raison: Parallélisable, GPU-friendly
   
   # Avec CuPy (CUDA Python)
   import cupy as cp
   gpu_array = cp.array([3, 1, 4, 1, 5, 9])
   sorted_gpu = cp.sort(gpu_array)  # Tri GPU optimisé

═══════════════════════════════════════════════════════════════
"""



[OK] ANTI-PATTERNS & ERREURS COURANTES


"""
[X] ERREURS À ÉVITER

1. Utiliser Bubble Sort pour grands tableaux
   [X] BAD:  bubble_sort(million_elements)
   [OK] GOOD: sorted(million_elements)

2. Modifier tableau original sans le vouloir
   [X] BAD:  def bad_sort(arr):
                arr.sort()  # Modifie l'original!
                return arr
   [OK] GOOD: def good_sort(arr):
                return sorted(arr)  # Retourne copie

3. Ignorer la stabilité du tri
   [X] BAD:  # Perd l'ordre des timestamps égaux
            quick_sort(transactions)
   [OK] GOOD: sorted(transactions, key=...)  # Stable

4. Trier plusieurs fois au lieu d'une fois
   [X] BAD:  sorted_by_x = sorted(data, key=lambda x: x[0])
            sorted_by_y = sorted(sorted_by_x, key=lambda x: x[1])
   [OK] GOOD: sorted(data, key=lambda x: (x[1], x[0]))

5. Utiliser tri par comparaison pour comptage
   [X] BAD:  sorted([1, 5, 2, 5, 1, 3])  # O(n log n)
   [OK] GOOD: counting_sort([1, 5, 2, 5, 1, 3])  # O(n)

6. Ne pas profiter de données presque triées
   [X] BAD:  merge_sort(nearly_sorted_data)
   [OK] GOOD: insertion_sort(nearly_sorted_data)  # O(n)

7. Tri en place quand copie nécessaire
   [X] BAD:  original = [3, 1, 2]
            result = original.sort()  # result est None!
   [OK] GOOD: result = sorted(original)  # Copie triée

8. Oublier les types de données
   [X] BAD:  counting_sort([1.5, 2.7, 3.2])  # Floats!
   [OK] GOOD: sorted([1.5, 2.7, 3.2])

9. Sur-optimisation prématurée
   [X] BAD:  Implémenter Quick Sort custom pour 10 éléments
   [OK] GOOD: Utiliser sorted() - déjà optimisé

10. Ignorer complexité spatiale
    [X] BAD:  merge_sort(data)  # O(n) espace sur embedded
    [OK] GOOD: heap_sort(data)   # O(1) espace
"""



[OK] RESSOURCES & RÉFÉRENCES


"""
[DOCS] DOCUMENTATION & APPRENTISSAGE

Official Python:
- https://docs.python.org/3/howto/sorting.html
- https://wiki.python.org/moin/HowTo/Sorting

Algorithmes classiques:
- Introduction to Algorithms (CLRS)
- The Art of Computer Programming Vol. 3 (Knuth)

Visualisations interactives:
- https://visualgo.net/sorting
- https://www.sorting-algorithms.com
- https://www.toptal.com/developers/sorting-algorithms

Comparaisons empiriques:
- https://github.com/python/cpython/blob/main/Objects/listsort.txt
  (Tim Peters' description of TimSort)

Benchmarks:
- https://github.com/sorting-algorithms/sorting-algorithms

Articles académiques:
- TimSort: https://drops.dagstuhl.de/opus/volltexte/2018/9467/
- IntroSort: Musser, D. R. (1997)

═══════════════════════════════════════════════════════════════

[COURS] EXERCICES PRATIQUES

1. Implémenter tri personnalisé pour objets complexes
2. Optimiser Quick Sort avec médiane de 3
3. Mesurer performance sur différents types de données
4. Implémenter tri stable vs non-stable
5. Créer visualisation animée d'un tri
6. Adapter Counting Sort pour nombres négatifs
7. Implémenter k-way merge pour tri externe
8. Comparer cache performance (Quick vs Merge)
9. Paralléliser Merge Sort avec multiprocessing
10. Implémenter tri adaptatif (auto-select algorithm)

═══════════════════════════════════════════════════════════════
"""



[OK] CONCLUSION & BEST PRACTICES


"""
[OBJECTIF] GUIDE DÉCISIONNEL FINAL

┌─────────────────────────────────────────────────────────────┐
│                    QUAND UTILISER QUOI                       │
└─────────────────────────────────────────────────────────────┘

[1er] PAR DÉFAUT (90% des cas):
   -> sorted() ou list.sort() de Python
   -> Raison: TimSort optimisé, stable, adaptatif

[2e] CAS SPÉCIAUX:

   Petits tableaux (n < 50):
   -> Insertion Sort
   
   Données presque triées:
   -> Insertion Sort (O(n) si presque trié)
   
   Mémoire très limitée:
   -> Heap Sort ou Quick Sort en place
   
   Garantie O(n log n) pire cas:
   -> Merge Sort ou Heap Sort
   
   Entiers petite plage:
   -> Counting Sort ou Radix Sort
   
   Données distribuées uniformément:
   -> Bucket Sort
   
   Tri externe (fichiers > RAM):
   -> External Merge Sort
   
   Parallélisation GPU:
   -> Bitonic Sort ou Odd-Even Sort
   
   Production C++/Java:
   -> IntroSort (C++ std::sort)
   -> TimSort (Java, Python)

═══════════════════════════════════════════════════════════════

[OK] CHECKLIST AVANT DE TRIER:

[WHITE_SQUARE] Taille des données? (petit/moyen/grand)
[WHITE_SQUARE] Type de données? (entiers/floats/objets)
[WHITE_SQUARE] Distribution? (aléatoire/presque trié/uniforme)
[WHITE_SQUARE] Mémoire disponible? (limitée/abondante)
[WHITE_SQUARE] Stabilité requise? (oui/non)
[WHITE_SQUARE] Performance critique? (temps réel/batch)
[WHITE_SQUARE] Plateforme? (CPU/GPU/embarqué)

═══════════════════════════════════════════════════════════════

[COURS] RÈGLES D'OR:

1. Don't reinvent the wheel - Utilisez sorted()
2. Mesurez avant d'optimiser
3. La simplicité bat la complexité
4. Connaissance des données > algorithme sophistiqué
5. O(n log n) suffit pour la plupart des cas
6. Stabilité importante pour tri multi-clés
7. Mémoire et cache matters
8. Tests > théorie pour performance réelle
9. Lisibilité > micro-optimisations
10. L'algorithme "parfait" n'existe pas - adaptez!

═══════════════════════════════════════════════════════════════

FIN DU CHEATSHEET - Bonne chance avec vos tris! [RAPIDE]
"""