| Les deux révisions précédentesRévision précédenteProchaine révision | Révision précédente |
| nsi:premiere:tableau:tris [2022/03/18 14:05] – goupillwiki | nsi:premiere:tableau:tris [2024/01/08 12:34] (Version actuelle) – [Ordres de grandeurs] goupillwiki |
|---|
| |
| Ceci considéré, que veut-on ? | Ceci considéré, que veut-on ? |
| * trier le tableau ''tab'' lui-même ? Dans ce cas on parle de **tri en place**. La fonction pas à renvoyer de tableau puisque le tableau trié est ''tab''. | * trier le tableau ''tab'' lui-même ? Dans ce cas on parle de **tri en place**. La fonction ne va pas à renvoyer de tableau puisque le tableau trié est ''tab''. |
| * fournir une copie de ''tab'' mais triée, ''tab'' restant inchangé. Dans ce cas, la fonction renvoie la copie triée. | * fournir une copie de ''tab'' mais triée, ''tab'' restant inchangé. Dans ce cas, la fonction renvoie la copie triée. |
| |
| Les langages fournisse le deux options : | Les langages fournisse les deux options : |
| <code python> | <code python> |
| >>> tab = [14, 8, 17, 22, 3, 9] | >>> tab = [14, 8, 17, 22, 3, 9] |
| [3, 8, 9, 14, 17, 22] | [3, 8, 9, 14, 17, 22] |
| >>> tab = [14, 8, 17, 22, 3, 9] | >>> tab = [14, 8, 17, 22, 3, 9] |
| >>> tab_ordre = sorted(tab) # crée une copie triée | >>> sorted(tab) # renvoie une copie triée |
| >>> tab_ordre | |
| [3, 8, 9, 14, 17, 22] | [3, 8, 9, 14, 17, 22] |
| >>> tab # n'a pas changé | >>> tab # n'a pas changé |
| Prenons l'exemple du tri de trois items ''abc''. Il y a six ordres possibles. En comparant les valeurs : a < b ? a < c ? b < c ? on peut déterminer l'ordre croissant. Ce graphique représente l'ensemble des cas. | Prenons l'exemple du tri de trois items ''abc''. Il y a six ordres possibles. En comparant les valeurs : a < b ? a < c ? b < c ? on peut déterminer l'ordre croissant. Ce graphique représente l'ensemble des cas. |
| |
| {{ :nsi:premiere:tableau:ordre_grandeur_tri.svg |}} | {{ nsi:premiere:tableau:ordre_grandeur_tri.svg |}} |
| |
| <WRAP tip>2 tests suffisent parfois. Les cas //bac// et //cba// ne sont pas spécialement plus simples. C'est seulement que nous avons choisi de tester a < b en premier et b < c en deuxième. On peut dire que si le bon tri était //bac// ou //cba// et que nous avons choisi de tester a < b puis b < c, on a fini en deux tests, on a eu de la chance de faire juste ce qu'il fallait. Mais on ne peut pas le prévoir d'avance.</WRAP> | <WRAP tip>2 tests suffisent parfois. Les cas //bac// et //cba// ne sont pas spécialement plus simples. C'est seulement que nous avons choisi de tester a < b en premier et b < c en deuxième. On peut dire que si le bon tri était //bac// ou //cba// et que nous avons choisi de tester a < b puis b < c, on a fini en deux tests, on a eu de la chance de faire juste ce qu'il fallait. Mais on ne peut pas le prévoir d'avance.</WRAP> |
| </WRAP> | </WRAP> |
| |
| <WRAP box>Pour un tableau de $n$ items, un algorithme ne pourra pas espérer faire moins que $\log_2(n!)$ comparaisons dans tous les cas. Les algorithmes que l'on propose en font généralement beaucoup plus !</WRAP> | <WRAP box>Pour un tableau de $n$ items, un algorithme ne pourra pas espérer faire moins que $\log_2(n!)$ comparaisons dans tous les cas. Pour $n$ assez grand, cela est comparable à $n\log_2(n)$. Certains algorithmes ont un coût de calcul du même ordre de grandeur et on sait qu'on ne pourra pas mieux faire. Les deux algorithmes que nous allons étudier en première (tri par sélection, tri par insertion) sont beaucoup moins efficace. Ce n'est pas gênant si le tableau à trier est de petite taille (jusqu'à 1000, ça va) mais pour de gros tableaux, ils deviennent inutilisables.</WRAP> |
| |
| ===== Notion de complexité ===== | ===== Notion de complexité ===== |
| Nous allons étudier deux algorithmes de tri. Ils ne sont pas les plus efficaces mais ils ont l'avantage d'être facile à comprendre car assez naturels. | Nous allons étudier deux algorithmes de tri. Ils ne sont pas les plus efficaces mais ils ont l'avantage d'être facile à comprendre car assez naturels. |
| |
| * [[nsi:premiere:tris_selection|Tri par sélection]] | * [[nsi:premiere:tableau:tri:selection|Tri par sélection]] |
| * [[nsi:premiere:tris_insertion|Tri par insertion]] | * [[nsi:premiere:tableau:tri:insertion|Tri par insertion]] |
| |
| |
| |
| |
