{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<span style=\"float:left;\">Licence CC BY-NC-ND</span><span style=\"float:right;\">Thierry Parmentelat & Arnaud Legout <img src=\"media/both-logos-small-alpha.png\" style=\"display:inline\"></span><br/>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tris de listes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Complément - niveau basique"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Python fournit une méthode standard pour trier une liste, qui s'appelle, sans grande surprise, `sort`. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Utilisation basique"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voyons comment se comporte `sort` sur un exemple simple."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"liste = [8, 7, 4, 3, 2, 9, 1, 5, 6]\n",
"print('avant tri', liste)\n",
"liste.sort()\n",
"print('apres tri', liste)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On retrouve ici, avec l'instruction `liste.sort()` un cas d'appel de méthode (ici `sort`) sur un objet (ici `liste`), comme on l'avait vu dans la vidéo sur la notion d'objet."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La première chose à remarquer est que la liste d'entrée a été modifiée, on dit \"en place\", ou encore \"par effet de bord\".\n",
"\n",
"On aurait pu imaginer que la liste d'entrée soit restée inchangée, et que la méthode de tri renvoie une copie triée de la liste, ce n'est pas le choix qui a été fait.\n",
"\n",
"De cette façon, c'est à l'utilisateur de la méthode de réaliser au préalable une copie de la liste initiale si c'est nécessaire dans son cas d'usage. On évite ainsi d'imposer une opération de copie, qui peut être coûteuse en mémoire, lorsque ce n'est pas utile."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Tri décroissant"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On remarque aussi que la liste est triée par ordre croissant. Si vous souhaitez au contraire l'ordre décroissant, vous pouvez le faire comme ceci:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"liste = [8, 7, 4, 3, 2, 9, 1, 5, 6]\n",
"print('avant tri', liste)\n",
"liste.sort(reverse=True)\n",
"print('apres tri décroissant', liste)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nous n'avons pas encore vu à quoi correspond cette formule `reverse=True` dans l'appel à la méthode - ceci sera approfondi dans le chapitre sur les appels de fonction - mais dans l'immédiat vous pouvez utiliser cette technique telle quelle."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Chaînes de caractères"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cette technique fonctionne très bien sur tous les types numériques (enfin, à l'exception des complexes; en guise d'exercice: pourquoi ?), ainsi que sur les chaînes de caractères:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"liste = ['spam', 'egg', 'bacon', 'beef']\n",
"liste.sort()\n",
"print('après tri', liste)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comme on s'y attend, il s'agit cette fois d'un **tri lexicographique**, dérivé de l'ordre total sur les caractères. En gros, c'est l'ordre du dictionnaire. Il faut souligner toutefois, pour les personnes n'ayant jamais été exposées à l'informatique, que cet ordre, quoique déterministe, est arbitraire en dehors des lettres de l'alphabet."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ainsi par exemple:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# deux caractères minuscules se comparent \n",
"# comme on s'y attend\n",
"'a' < 'z'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Bon; mais par contre:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# si l'un est en minuscule et l'autre en majuscule, \n",
"# ce n'est plus le cas\n",
"'Z' < 'a'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce qui à son tour explique ceci:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# la conséquence de 'Z' < 'a', c'est que\n",
"liste = ['abc', 'Zoo']\n",
"liste.sort()\n",
"print(liste)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et lorsque les chaines contiennent des espaces ou autres ponctuations, le résultat du tri peut paraître surprenant:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# attention ici notre premiere chaine commence par un espace\n",
"# et le caractère 'Espace' est plus petit \n",
"# que tous les autres caractères imprimables\n",
"liste = [' zoo', 'ane']\n",
"liste.sort()\n",
"print(liste)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### À suivre"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Il est possible de définir soi-même le critère à utiliser pour trier une liste, et nous verrons cela très bientôt une fois que nous aurons introduit la notion de fonction."
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
},
"livereveal": {
"auto_select": "code",
"auto_select_fragment": true,
"autolaunch": false,
"backimage": "media/nologo.png",
"height": "100%",
"slideNumber": "c",
"start_slideshow_at": "selected",
"theme": "simple",
"transition": "fade",
"width": "100%"
},
"notebookname": "Tris de listes",
"version": "3.0"
},
"nbformat": 4,
"nbformat_minor": 1
}