{"id":1203,"date":"2025-05-11T08:28:00","date_gmt":"2025-05-11T06:28:00","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1203"},"modified":"2025-05-12T07:39:21","modified_gmt":"2025-05-12T05:39:21","slug":"nsi-listes-et-algorithmes-de-tris","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/nsi-listes-et-algorithmes-de-tris\/","title":{"rendered":"NSI : listes et algorithmes de tris"},"content":{"rendered":"\n

1. M\u00e9thodes de tris<\/h2>\n\n\n\n

Pour pouvoir \u00e9tudier des donn\u00e9es, il est souvent n\u00e9cessaire de les trier par ordre croissant ou d\u00e9croissant.
Il existe diff\u00e9rentes m\u00e9thodes pour cela.
Ces algorithmes diff\u00e8rent par leurs complexit\u00e9s et leurs efficacit\u00e9s.
Pour visualiser diff\u00e9rents algorithmes de tri :
https:\/\/www.toptal.com\/developers\/sorting-algorithms<\/a><\/p>\n\n\n\n

Pour r\u00e9viser et d\u00e9couvrir d’autres algorithmes de tris ;<\/p>\n\n\n\n

l’article sur les algorithmes de tris<\/a><\/p>\n\n\n\n

2. Tri par s\u00e9lection<\/h3>\n\n\n\n

Un premier fichier pr\u00e9sentant les 3 algorithmes de tris vus en cours :<\/p>\n\n\n\n

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    for i in range(len(liste)-1):\n        # pour voir le d\u00e9roulement de l'algorithme\n        # print(a)\n        indice_min=i\n        for j in range(i,len(liste)):\n            if a[j]<a[indice_min]:\n                indice_min=j\n        a[i],a[indice_min]=a[indice_min],a[i]\n    return a\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]<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\n\n<\/code><\/pre>\n\n\n\n
3. Tri par insertion<\/h2>\n\n\n\n
def tri_insertion(a):\n    # trie une liste par ordre croissant\n    # par l'algo de tri par insertion\n    for i in range(0,len(liste)-1):\n        j=i+1\n        val=a[j]\n        while j>0 and a[j-1]>val:\n            a[j]=a[j-1]\n            j=j-1\n            \n        a[j]=val\n        #print(i,j,a)\n<\/code><\/pre>\n\n\n\n
4. Comparer des m\u00e9thodes de tris<\/h2>\n\n\n\n
Un programme permettant de comparer le temps mis par ces diff\u00e9rents algorithmes :<\/p>\n\n\n\n
import tris\nfrom timeit import timeit\nimport pylab\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.savefig(\"graphique \"+type_tri+\".png\")\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(\"graphique comparaisons.png\")\n    pylab.show()\n\n\n\ncomparaison_tris(1000)\n<\/code><\/pre>\n\n\n\n