B n]0@sddlTddZddZddZdadd Zd d Zd d Zedededede e dZ x`e dks~e dkre e dZ e d Zeee Zede dkr*e d ZedkreeZn0edkreeZnedkreeZn eeZdaedeededeedneeedZx|edD]pZed eeZeeeZed!ed"eejd#ed$ed%eeded&eedq@Wed!e e dZ qlWed'e d(d S)))*cCst|}d}d}xvt|dD]f}|}x2t|d|D] }|d7}||||kr6|}q6W||kr|d7}||||||<||<qW||gS)u0Trie une liste de nombres de manière croissanter)lenrange)listen nbre_comp nbre_echangeiindexjr p/Users/jerome/SynologyDrive/College/Informatique/OCI/1_Site/2_Algorithmique/1_Tri/documents/AnalyseComplexite.py TriSelection srcCsd}d}xtdt|D]~}||}|}xD|dkrl||d|krl|d7}|d7}||d||<|d}q*W|dkr~|d7}||kr|d7}|||<qW||gS)u0Trie une liste de nombres de manière croissanterr)rr)rrZ nbre_deplr eltZpositionr r r TriInsertion$s   rcCsd}d}xttt|dddD]\}xVt|D]J}|d7}||||dkr,||d||||<||d<|d7}q,WqW||gS)u0Trie une liste de nombres de manière croissanterr)rr)rrr r r r r r TriBullesBs"rcCsg}d}}t|}t|}x||krv||krvtd7a||||kr^||||d7}q||||d7}q||kr|||d7}Pq|||d7}PqW|S)Nrr)rcompappend)Zliste1Zliste2rr r Zn1Zn2r r rfusion[s$  rcs$fdd||dd<tdgS)u[ TriFusion(list liste) -> None Trie la liste de nombres de manière croissante csBt|dkr|St|dt|d|t|ddS)N)rr)r)TriFusionInterner rrs z#TriFusion..TriFusionInterneNzsans signification dans ce cas.)r)rr )rr TriFusionzs rcCsg}|dkr6x$t|D]}|tdd|qW|S|dkr^xt|D]}||qHW|Sx"t|D]}||d|qhW|SdS)uZ Génère une liste de type (aléatoire, croissante ou décroissante) et de taille donnésArrCrN)rrrandint)Z type_listtailleresultr r r r generate_listsrugCe programme permet d'analyser la complexite des 4 algorithmes de tri élémentaires étudies en cours.upEn sélectionnant l'option 1, vous pourrez analyser un algorithme particulier sur un type de listes particulier.ubEn sélectionnant l'option 2, vous pourrez analyser les 3 algorithmes sur un même type de listes.u:En sélectionnant l'option 3, vous terminez le programme. z$Choisissez une option entre 1 et 3 :rrz%Entrez la taille de la liste cobaye: uQEntrez le type de la liste cobaye ((A)léatoire, (C)roissante, (D)écroissante) :zVotre liste est generee...uWChoisissez l'algorithme à appliquer ((B)ulles, (I)insertion, (S)élection), (F)usion :BISuALe nombre de comparaisons réalisees par l'algorithme choisi est uKLe nombre de déplacements/échanges réalises par l'algorithme choisi est )rrrN uRésultats pour le tri avec z :z'************************************** u*Le nombre de comparaisons réalisées est u4Le nombre de déplacements/échanges réalisés est z Goodbye...u0Appuyez sur une touche pour fermer la fenêtre !)randomrrrrrrrprintintinputoptionrupperZ type_listerZalgoZ complexitestrZ algorithmerr rtest__name__r r r rsT