{"id":1005,"date":"2017-03-31T01:44:59","date_gmt":"2017-03-30T23:44:59","guid":{"rendered":"http:\/\/www2.mathnique.com\/site\/?page_id=1005"},"modified":"2020-01-12T17:44:29","modified_gmt":"2020-01-12T16:44:29","slug":"algorithmes-de-tri","status":"publish","type":"page","link":"https:\/\/www.mathnique.com\/site\/algorithmes-de-tri\/","title":{"rendered":"Algorithmes de tri ; performances."},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-1032 aligncenter\" src=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/cartestriees.png\" alt=\"\" width=\"275\" height=\"297\" \/><\/p>\n<p>Tout programmeur est confront\u00e9 un jour \u00e0 la n\u00e9cessit\u00e9 de faire appel \u00e0 un programme de tri de donn\u00e9es par exemple, trier les noms d'une liste, classer des nombres dans l'ordre croissant,...<br \/>\nIl existe une quantit\u00e9 impressionnante de tris. Voici quelques-uns des plus classiques.<\/p>\n<ul>\n<li><span style=\"color: #ff0000;\"><strong>Tri Bulles<\/strong><br \/>\n<em>Principe :\u00a0<\/em><br \/>\n<\/span>Soit un tableau de $n$ entiers.<br \/>\nOn compare successivement $2$ \u00e9l\u00e9ments cons\u00e9cutifs en partant du dernier \u00e9l\u00e9ment.<br \/>\nChaque fois que deux \u00e9l\u00e9ments ne sont pas dans l'ordre voulu, on les \u00e9change.<br \/>\nApr\u00e8s un examen de tous les couples, l'\u00e9l\u00e9ment le plus petit se retrouve en 1\u00e8re position.<br \/>\nOn recommence pour les $n - 1$ derniers \u00e9l\u00e9ments afin d'amener le plus petit d'entre eux en deuxi\u00e8me position.<br \/>\nApr\u00e8s au plus $ n - 1$ examens, le tableau est tri\u00e9.<br \/>\nOn appelle ce tri du nom de <em>tri bulle (en anglais bubble sort)<\/em> car les plus petits \u00e9l\u00e9ments remontent petit \u00e0 petit \u00e0 leur place.<br \/>\n<span style=\"color: #ff0000;\"><em>Algorithme \u00a0: <a href=\"http:\/\/www.mathnique.com\/site\/wp-content\/uploads\/2020\/01\/tribulles.pdf\">tribulles<\/a><\/em><br \/>\n<em>Complexit\u00e9<\/em> :<br \/>\n<\/span>- Quel est le meilleur des cas ?<br \/>\nD\u00e9terminer en fonction de $n$ le nombre $N_{min}$ de comparaisons \u00e0 faire pour trier le tableau $T$ <span style=\"color: #ff0000;\"><br \/>\n<\/span>- Quel est le pire\u00a0 des cas ?<br \/>\nD\u00e9terminer en fonction de $n$ le nombre $N_{max}$ de comparaisons \u00e0 faire pour trier le tableau $T$<\/li>\n<li><strong><span style=\"color: #ff0000;\">Tri s\u00e9lection<\/span><\/strong>\n<ul>\n<li><span style=\"color: #008000;\"><strong>S\u00e9lection du maximum<\/strong><\/span><br \/>\n<em><span style=\"color: #ff0000;\">Principe :<\/span><\/em><br \/>\nSoit un tableau $T[1],T[2],\\cdots,T[n]$<br \/>\nOn recherche le plus grand \u00e9l\u00e9ment soit par exemple $T[i]$.<br \/>\nOn \u00e9change alors $T[j]$ et $T[n]$.<br \/>\nOn recommence cette d\u00e9marcha sur le reste du tableau\u00a0$T[1],T[2],\\cdots,T[n - 1]$<br \/>\npuis sur\u00a0\u00a0$T[1],T[2],\\cdots,T[n - 2]$ etc ... jusqu'\u00e0 qu'il ne reste plus qu'un seul \u00e9l\u00e9ment le plus petit.<br \/>\n<em><span style=\"color: #ff0000;\">Algorithme :<\/span><\/em>\u00a0<a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/triselectionmax.pdf\">triselectionmax<\/a><\/li>\n<li><span style=\"color: #008000;\">S\u00e9lection du minimum<\/span><br \/>\n<em><span style=\"color: #ff0000;\">Principe :\u00a0<\/span><\/em><br \/>\nSoit un tableau $T[1],T[2],\\cdots,T[n]$<br \/>\nOn recherche le plus petit\u00a0\u00e9l\u00e9ment soit par exemple $T[i]$.<br \/>\nOn \u00e9change alors $T[j]$ et $T[1]$.<br \/>\nOn recommence cette d\u00e9marcha sur le reste du tableau\u00a0$T[2],T[3],\\cdots,T[n]$<br \/>\npuis sur\u00a0\u00a0$T[3],T[4],\\cdots,T[n]$ etc ... jusqu'\u00e0 qu'il ne reste plus qu'un seul \u00e9l\u00e9ment le plus grand.<br \/>\n<em><span style=\"color: #ff0000;\">algorithme<\/span> <\/em>:\u00a0<a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/triselectionmin.pdf\">triselectionmin<\/a><\/li>\n<li><em><span style=\"color: #ff0000;\">Complexit\u00e9 :<\/span><\/em><br \/>\nD\u00e9terminer en fonction de $n$ le nombre $N$ de comparaisons \u00e0 faire pour trier le tableau $T$.<br \/>\nJustifier.<br \/>\nSi l'on prend comme param\u00e8tre la taille $n$ des donn\u00e9es et comme op\u00e9ration \u00e9l\u00e9mentaire la comparaison, d\u00e9terminer la complexit\u00e9 de cet algorithme en temps $t$ d'ex\u00e9cution.<\/li>\n<\/ul>\n<\/li>\n<li><span style=\"color: #ff0000;\"><strong>Tri par insertion<\/strong><\/span><\/li>\n<li><strong><span style=\"color: #ff0000;\">Tri baquets (Mines Ponts 2004)<\/span><\/strong>\n<ul>\n<li><em><span style=\"color: #ff0000;\">Sujet :\u00a0<a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/minespontsinfo04.pdf\">minespontsinfo04<\/a><\/span><\/em><\/li>\n<li><span style=\"color: #ff0000;\"><em>Corrig\u00e9 en Caml: <a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/mines04infocor.pdf\">mines04infocor<\/a><br \/>\nCorrig\u00e9 personnel en Pascal :\u00a0<a href=\"http:\/\/www.mathnique.com\/site\/wp-content\/uploads\/2020\/01\/tribaquets.pdf\">tribaquets<\/a><br \/>\n<\/em><\/span><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Tout programmeur est confront\u00e9 un jour \u00e0 la n\u00e9cessit\u00e9 de faire appel \u00e0 un programme de tri de donn\u00e9es par exemple, trier les noms d'une liste, classer des nombres dans l'ordre croissant,... Il existe une quantit\u00e9 impressionnante de tris. Voici quelques-uns des plus classiques. Tri Bulles Principe :\u00a0 Soit un tableau de $n$ entiers. On &hellip; <a href=\"https:\/\/www.mathnique.com\/site\/algorithmes-de-tri\/\" class=\"more-link\">Continuer la lecture<span class=\"screen-reader-text\"> de &laquo;&nbsp;Algorithmes de tri ; performances.&nbsp;&raquo;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"class_list":["post-1005","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1005","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/comments?post=1005"}],"version-history":[{"count":18,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1005\/revisions"}],"predecessor-version":[{"id":2960,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1005\/revisions\/2960"}],"wp:attachment":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/media?parent=1005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}