NSI · TERMINALETrieret mesurer le coûtinsertion, sélection, fusion, rapideMESURERLa complexitéOn compte les opérations élémentaires,ici les comparaisons, selon n,la taille des données.On garde l'ordre de grandeur, dans le pire des cas.ncomparaisonsn²n log₂ nTRI PAR INSERTIONInsérer à sa placeO(n²)524613départ254613on insère 2245613on insère 4245613on insère 6124563on insère 1123456on insère 3Tableau à l'envers : 1 + 2 + … + (n − 1)soit environ n²/2 comparaisons.Tableau déjà trié : n comparaisons seulement.TRI PAR SÉLECTIONChercher le minimumO(n²)524613départ124653minimum 1 en place 1124653minimum 2 en place 2123654minimum 3 en place 3123456minimum 4 en place 4123456minimum 5 en place 5Toujours n(n − 1)/2 comparaisons,même si le tableau est déjà trié.1945 · VON NEUMANN, EDVACLe tri fusionDiviser pour régner52461387524613875246138752461387254613782456137812345678diviserfusionnerlog₂ n niveaux × n opérations = n log₂ nToujours O(n log n), mais un tableau annexe.Programme de fusion de von Neumann, 1945 (Knuth, 1970)1961 · HOARELe tri rapidePartitionner52461387pivot : 524135687plus petits à gauche,plus grands à droite12345678chaque partie, de mêmeEn moyenne : O(n log n), et sans tableau annexe.Pire cas, pivot toujours au bord : O(n²).Imaginé à Moscou en 1959, publié en 1961.En pratique, souvent le plus rapide.CHOISIRCe que coûte n²Donc…n = 1 000 000 donnéesn²10¹² comparaisonsn log₂ n≈ 2 × 10⁷environ 50 000 fois moins de travailAucun tri par comparaisons ne fait mieuxque n log n dans le pire des cas.Python trie avec Timsort, qui profite de l'ordre déjà là.À RETENIRLa complexitéle nombre d'opérations selon n,dans le pire des casO(n²)insertion et sélection : simples,mais trop lents sur de grandes donnéesO(n log n)fusion (von Neumann, 1945), toujours ;rapide (Hoare, 1961), en moyenneChoisirn log n est le mieux possible par comparaisons ;peser aussi la mémoire et le pire casJLjeromelabbe.frFiches de connaissance · NSI, TerminaleJL