{"id":1238,"date":"2020-06-11T12:01:35","date_gmt":"2020-06-11T10:01:35","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1238"},"modified":"2020-09-09T19:17:00","modified_gmt":"2020-09-09T17:17:00","slug":"comparaison-de-tris","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/comparaison-de-tris\/","title":{"rendered":"Comparaison  de tris"},"content":{"rendered":"\n<h2>1. Comparaison temps d&rsquo;ex\u00e9cution<\/h2>\n\n\n\n<p>Une mani\u00e8re empirique de d\u00e9terminer quel est l&rsquo;algorithme de tris le plus efficace entre le tri par insertion, le tri par bulles et le tri par s\u00e9lection est de comparer leur temps d&rsquo;ex\u00e9cution pour un certain nombre de tris de listes al\u00e9atoires de tailles donn\u00e9es.<\/p>\n\n\n\n<p>Dans votre fichier comportant vos diff\u00e9rentes fonctions , on ajoute la fonction tri_sort()<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>from random import randint\n\ndef liste_aleatoire(n):\n   \n\ndef inverse_liste(a):\n   \n\ndef triee(a):\n    \n\ndef tri_selection(a):\n    \n\ndef tri_bulles(a):\n    \ndef tri_insertion(a):\n    \n\ndef tri_sort(a):\n    b=a.copy()\n    b.sort()\n    return b\n<\/code><\/pre>\n\n\n\n<p>Copier et coller le script suivant dans un fichier situ\u00e9 dans le m\u00eame r\u00e9pertoire que votre script de tris.<\/p>\n\n\n\n<p>Modifier la 1ere ligne du script en rempla\u00e7ant si besoin tris par le nom du module comportant vos algorithmes de tris.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import tris\nfrom timeit import timeit\nimport pylab\n\n\n\n\n#timeit(setup='from tris import tri_select; from listes import cree_liste_melangee',stmt='tri_select(cree_liste_melangee(10))',number=100)\n\ndef mesure_temps(tri,longueur):\n    '''\n    retourne le temps maximal pour trier par tri par s\u00e9lection de 100 listes m\u00e9lang\u00e9es de longueur 10\n    : longueur : (int) longueur des listes \u00e0 trier\n    : CU :\n    : return : (list) une liste contenant le temps des listes de longueurs 1,2,......, longueur\n    \n    '''\n    liste_temps=[]\n    for i in range(0,longueur):\n        temp = timeit(setup='from tris import '+ tri +'; from tris import liste_aleatoire',stmt=tri+'(liste_aleatoire('+str(i)+'))',number=100)\n        liste_temps.append(temp)\n    return liste_temps\n\n\ndef affichage(type_tri,longueur):\n    '''\n    affiche le graphique repr\u00e9sentant les temps maximums pour 100 listes tri\u00e9es de taille donn\u00e9e\n    '''\n    \n    correspondance = {# on cr\u00e9e un dictionnaire de correspondances\n    \"selection\":\"tri_selection\", # \n    \"insertion\":\"tri_insertion\",\n    \"bulles\":\"tri_bulles\",\n    \"sort\":\"tri_sort\",\n    }\n    \n\n    longueur_listes=[i for i in range(1,longueur+1)]\n    # return correspondance[type_tri]\n    liste_temps=mesure_temps(correspondance[type_tri],longueur)\n    NBRE_ESSAIS = 100\n    pylab.title('Temps du tri '+type_tri+' (pour {:d} essais)'.format(NBRE_ESSAIS))\n    pylab.xlabel('taille des listes')\n    pylab.ylabel('temps en secondes')\n    pylab.grid()\n    pylab.plot(longueur_listes,liste_temps)\n    pylab.show()\n\ndef comparaison_tris(longueur):\n    longueur_listes=[i for i in range(1,longueur+1)]\n    # return correspondance[type_tri]\n    NBRE_ESSAIS = 100\n    pylab.title('Temps cumul\u00e9 pour trier {:d} listes al\u00e9atoires,'.format(NBRE_ESSAIS)+'\\npour des listes de longueurs 1 \u00e0 '+str(longueur)+'.')\n    pylab.xlabel('taille des listes')\n    pylab.ylabel('temps en secondes \\npour {:d} listes '.format(NBRE_ESSAIS))\n    pylab.grid()\n    pylab.plot(longueur_listes,mesure_temps(\"tri_selection\",longueur),label=\"tri_selection\")\n    pylab.plot(longueur_listes,mesure_temps(\"tri_insertion\",longueur),label=\"tri_insertion\")\n    pylab.plot(longueur_listes,mesure_temps(\"tri_bulles\",longueur),label=\"tri_bulles\")\n    pylab.plot(longueur_listes,mesure_temps(\"tri_sort\",longueur),label=\"tri_sort\")\n    pylab.legend()\n    pylab.savefig(\"graphique1.png\")\n    pylab.show()\n\n\n\naffichage(\"selection\",100)<\/code><\/pre>\n\n\n\n<p>On obtient alors :<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"432\" height=\"288\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-selection.png\" alt=\"\" class=\"wp-image-1242\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-selection.png 432w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-selection-300x200.png 300w\" sizes=\"(max-width: 432px) 100vw, 432px\" \/><\/figure>\n\n\n\n<p>affichage(\u00ab\u00a0bulles\u00a0\u00bb,100) donnera :<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"432\" height=\"288\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-bulles.png\" alt=\"\" class=\"wp-image-1243\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-bulles.png 432w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-bulles-300x200.png 300w\" sizes=\"(max-width: 432px) 100vw, 432px\" \/><\/figure>\n\n\n\n<p>comparaison_tris(100)<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"432\" height=\"288\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-comparaisons.png\" alt=\"\" class=\"wp-image-1244\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-comparaisons.png 432w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/graphique-comparaisons-300x200.png 300w\" sizes=\"(max-width: 432px) 100vw, 432px\" \/><\/figure>\n\n\n\n<p>A vous de tester vos scripts et de les optimiser \u00e9ventuellement.<\/p>\n\n\n\n<h2>2. Proposition corrections algorithmes de tris<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>from random import randint\n\ndef liste_aleatoire(n):\n    # g\u00e9n\u00e9rer al\u00e9atoirement un liste de taille n\n    # contenant des nbres entiers entre 0 et 100\n    return [randint(0,100) for i in range(n)]\n\ndef inverse_liste(a):\n    # inverse les termes de la liste\n    retour=[]\n    for i in range(len(a)):\n        retour.append(a[len(a)-1-i])\n    return retour\n\ndef triee(a):\n    # indique si une liste est tri\u00e9e\n    for i in range(len(a)-1):\n        if a[i]>a[i+1]:\n            return False\n    return True\n\ndef tri_selection(a):\n    # trie une liste par ordre croissant\n    # par l'algo de tri par selection\n    liste=a.copy()\n    for i in range(len(liste)-1):\n        # pour voir le d\u00e9roulement de l'algorithme\n        # print(liste)\n        indice_min=i\n        for j in range(i,len(liste)):\n            if liste[j]&lt;liste[indice_min]:\n                indice_min=j\n        liste[i],liste[indice_min]=liste[indice_min],liste[i]\n    return liste\n\ndef tri_bulles(a):\n    # trie une liste par ordre croissant\n    # par l'algo de tri par bulle\n    liste=a.copy()\n    for i in range(len(liste)):\n        # pour voir le d\u00e9roulement de l'algorithme\n        #print(liste)\n        for j in range(len(liste)-1):\n            if liste[j+1]&lt;liste[j]:\n                liste[j+1],liste[j]=liste[j],liste[j+1]\n                # pour voir le d\u00e9roulement de l'algorithme\n                #print(liste)\n    return liste\n\ndef tri_insertion(a):\n    # trie une liste par ordre croissant\n    # par l'algo de tri par insertion\n    liste=a.copy()\n    for i in range(0,len(liste)-1):\n        \n        j=i+1\n        val=liste[j]\n        while j>0 and liste[j-1]>val:\n            liste[j]=liste[j-1]\n            j=j-1\n            \n        liste[j]=val\n        #print(i,j,liste)\n            \n                \n    return liste\n\ndef tri_sort(a):\n    b=a.copy()\n    b.sort()\n    return b\n\n# Pour tester les tris et comprendre leurs diff\u00e9rents fonctionnements\n#a=liste_aleatoire(10)\n#print(a)\n#print(\"Tri selection\")\n#tri_selection(a)\n#print(\"tri bulles\")\n#tri_bulles(a)\n#print(\"tri insertion\")\n#print(tri_insertion(a))\n#print(tri_sort(a))\n<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"800\" height=\"600\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/comparaisons.png\" alt=\"\" class=\"wp-image-1245\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/comparaisons.png 800w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/comparaisons-300x225.png 300w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/comparaisons-768x576.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>1. Comparaison temps d&rsquo;ex\u00e9cution Une mani\u00e8re empirique de d\u00e9terminer quel est l&rsquo;algorithme de tris le&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/labodemaths.fr\/WordPress3\/comparaison-de-tris\/\">Read the post<span class=\"screen-reader-text\">Comparaison  de tris<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1245,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1238"}],"collection":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/comments?post=1238"}],"version-history":[{"count":2,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1238\/revisions"}],"predecessor-version":[{"id":1247,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1238\/revisions\/1247"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1245"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1238"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1238"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}