{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## 3.4  Trier une table\n",
    " \n",
    "### 3.4.1. Tri d’une liste simple\n",
    "\n",
    "Dans la partie consacrée aux types construits, au 2.4.2 Opérations liées au caractère mutable des listes, on a rencontré la méthode sort( ) :\n",
    "\n",
    "     usage : nom_liste.sort(key=None, reverse=False)\n",
    "     \n",
    "Cette méthode peut prendre deux paramètres (optionnels). \n",
    "\n",
    "Concernant la paramètre *reverse*, qui est par défaut à *False*, c’est lui qui permet de choisir le sens du tri.\n",
    "\n",
    "Par défaut, reverse étant à False (= à l’envers = Faux) *le tri se fait donc en sens croissant*. \n",
    "\n",
    "Pour avoir le *tri en sens décroissant* on devra écrire :\n",
    "\n",
    "  **nom_liste.sort(reverse=True)**\n",
    "  \n",
    "Cette méthode réalise le **tri « en place »**: la liste est modifiée suite à l’application de cette méthode (on utilise ici le caractère muable de la liste) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls =[3,1,4,5,2,8,0]\n",
    "ls.sort()\n",
    "print(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls =[3,1,4,5,2,8,0]\n",
    "ls.sort(reverse=True)\n",
    "print(ls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "On voit bien que la liste ls est modifiée par la méthode sort( )\n",
    "\n",
    "Il existe aussi une fonction native de Python du nom de **sorted( )** applicable à tout objet itérable qu’il soit muable ou non. En effet cette fonction **renvoie un nouvel itérable du même type mais trié**, ce qui fait que l’itérable initial n’est pas modifié.\n",
    "\n",
    "     usage : sorted(nom_itérable, key=None, reverse=False)\n",
    "     \n",
    "              renvoie un nouvel itérable\n",
    "              \n",
    "Essayer ces quelques lignes et les analyser :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls = [3,1,4,5,2,8,0]\n",
    "print(ls)\n",
    "ls2 = sorted(ls)\n",
    "print('ls2 = ', ls2)\n",
    "print('ls = ', ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls3 = sorted(ls2, reverse=True)\n",
    "print('ls3 = ', ls3)\n",
    "print('ls2 = ', ls2)\n",
    "print('ls = ', ls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selon la finalité, on choisira soit de trier la liste en place (méthode sort( )) soit d’en faire une copie triée (fonction sorted( )).\n",
    "\n",
    "### 3.4.2. Tri d’une liste d’itérables\n",
    "\n",
    "On va prendre le cas qui nous concerne : une liste de dictionnaires :\n",
    "\n",
    "Essayons la fonction **sorted( )** sur une petite liste de dictionnaires :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'}]\n",
    "\n",
    "tri_vol = sorted(vols)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On obtient une erreur...ce qui est bien normal si on y réfléchit un instant : que voudrait dire « trier des dictionnaires ». On veut trier les données par vol, par heure, par numéro de vol par compagnie ? ou successivement par plusieurs de ces critères ?\n",
    "\n",
    "C’est là qu’intervient le **paramètre optionnel key (la ‘clé’)** que l’on avait omis dans le paragraphe précédent (par défaut key=None : pas de clé) et qui va servir à donner le critère de tri.\n",
    "\n",
    "Attention c’est un peu technique… On ne donne pas directement le critère selon lequel on veut trier… ce serait trop simple ! Imaginons que l’on veuille trier cette table de vols selon le critère compagnie :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'}]\n",
    "\n",
    "tri_vol = sorted(vols,key='compagnie')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " … pas de chance !\n",
    " \n",
    "La documentation Python donne :\n",
    "\n",
    "key spécifie une fonction d'un argument utilisé pour extraire une clef de comparaison de chaque élément de l'itérable (par exemple, key=str.lower). La valeur par défaut est None (compare les éléments directement).\n",
    "\n",
    "… comprendre : key sert à préciser une fonction qui va être appliquée à chaque élément de la liste (ici à chaque dictionnaire) avant d’appliquer le tri. \n",
    "\n",
    "Cela pourrait-être par exemple **key=len** : len est une fonction native de Python qui mesure la longueur d’un itérable (le nombre de caractères dans une chaîne, le nombre d’éléments dans une liste…). \n",
    "\n",
    "Avec cette clé, le tri se ferait donc sur ce paramètre. len étant native, on n’a pas besoin de la définir :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lstr = ['un', 'deux', 'trois','quatre', 'cinq', 'six', 'sept', 'huit', 'neuf', 'dix']\n",
    "lstr_trie = sorted(lstr,key=len)    # on trie la liste lstr sur le critère longueur des chaînes qui la constituent\n",
    "\n",
    "# Afficher la liste ainsi triée :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analysons attentivement le résultat :\n",
    "\n",
    "    • le tri s’est bien fait selon le nombre ( len ) de caractères qui constituait chaque chaîne de caractères :\n",
    "        ◦ d’abord 2 caractères : ‘un’\n",
    "        ◦ puis 3 : ‘six’, ‘dix’\n",
    "        ◦ puis 4 : 'deux', 'cinq', 'sept', 'huit', 'neuf'\n",
    "        ◦ puis 5 : 'trois',\n",
    "        ◦ et enfin 6 :  'quatre'\n",
    "        \n",
    "    • lorsque deux éléments comparés avaient le même nombre de caractères, alors ils ont été rangés dans l’ordre dans lequel ils étaient initialement : cette deuxième remarque est très importante. \n",
    "   \n",
    "   **C’est la propriété dite de stabilité (on dit aussi que le tri est stable). Cette propriété n’est pas vraie pour tous les types de tris. Quand un tri possède cette propriété, cela implique que l’on pourra faire plusieurs tris successifs sur des critères différents.**\n",
    "   \n",
    "Reprenons notre tri sur le critère alphabétique des compagnies. On va devoir créer une fonction spécifique. Appelons-la ‘comp’ (abréviation pour ‘compagnie’ : on aurait pu l’appeler ‘compagnie’ mais pour éviter des confusions dans cette initiation on a préféré ce choix) : \n",
    "\n",
    "```Python\n",
    "def comp(elt):\n",
    "\n",
    "    return elt['compagnie']\n",
    "```\n",
    "    \n",
    "Dans la fonction de tri ‘sorted’, cette fonction ‘comp’ sera appelée successivement sur chaque élément de la liste ‘vols’ c’est à dire sur chacun des dictionnaires avec key=comp.\n",
    "return elt\\[‘compagnie’] signifiant de donner à key la valeur de l’attribut ‘compagnie’ pour le dictionnaire analysé :\n",
    "\n",
    "    • premier dictionnaire de la liste ‘vols’ : → EASYJET\n",
    "    • deuxième dictionnaire de la liste ‘vols’ : → AUSTRIAN AIRLINES\n",
    "    • troisième dictionnaire de la liste ‘vols’ : → BRITISH AIRLINES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'}]\n",
    "\n",
    "def comp(elt):\n",
    "    return elt['compagnie']\n",
    "\n",
    "tri_vol = sorted(vols,key=comp)    # ici reverse a sa valeur par défaut : False, donc tri de A vers Z\n",
    "\n",
    "# afficher le résultat :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Essayons maintenant le tri par compagnie en sens inverse :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'}]\n",
    "\n",
    "def comp(elt):\n",
    "    return elt['compagnie']\n",
    "\n",
    "# compléter le code :\n",
    "\n",
    "# afficher le résultat :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On souhaite maintenant afficher les vols selon un ordre horaire. \n",
    "\n",
    "Deux problèmes se posent :\n",
    "\n",
    " - l'horaire d'un vol est **réparti dans deux attributs** : 'heure' d'une part et 'minute' d'autre part...\n",
    " - dans un csv les **valeurs des attributs sont de type chaîne de caractères**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# problème du tri de grandeurs numériques stockées comme chaînes de caractères :\n",
    "lstr = ['25', '12', '3', '10']\n",
    "lstr_trie = sorted(lstr)\n",
    "print(lstr_trie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il faut donc convertir en nombre ces chaînes de caractères. \n",
    "\n",
    "On devra **réfléchir sur le type** dans lequel on va faire la conversion : **de l'entier ou du flottant** ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# problème du tri de grandeurs numériques stockées comme chaînes de caractères :\n",
    "lstr = ['25', '12', '3', '10']\n",
    "# sur cet exemple on peut s'en sortir de façon simple en passant au paramètre 'key' la fonction native \n",
    "# de conversion 'int()' qui transforme un nombre codé en str en son équivalent numérique \n",
    "lstr_trie = sorted(lstr, key=int)\n",
    "print(lstr_trie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarque importante : \n",
    "si **'3'** est remplacé par **'03'**, le simple tri sans imposer la conversion précédente avec key=int va fonctionner...(exécuter la cellule ci-dessous pour s'en convaincre)\n",
    "\n",
    "**MAIS IL FAUT ABSOLUMENT EVITER DE SE CONTENTER DE CETTE FACILITE...ET S'IMPOSER DE REALISER LA CONVERSION DE TYPE !**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remarque : si '3' est remplacé par '03' :\n",
    "lstr = ['25', '12', '03', '10']\n",
    "# le simple tri sans imposer la conversion précédente fonctionne :\n",
    "lstr_trie = sorted(lstr)\n",
    "print(lstr_trie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# essayer avec une liste dont les éléments sont des flottants représentés avec un type str :\n",
    "lstr = ['25.0', '12.4', '12.3', '12.5', '3.1']\n",
    "# compléter le code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Revenons sur le tri des vols d'avion selon le critère horaire. \n",
    "On a ajouté des vols supplémentaires à la liste.\n",
    "\n",
    "Il faudra faire **deux tris successifs** sur le critère **'heure'** et sur le critère **'minute'**:\n",
    " - dans un premier temps on pourra se contenter de réaliser ce double tri sans faire de conversion\n",
    " - tester ce qui se passe si on fait d'abord le tri sur les heures puis sur les minutes ou si on fait l'inverse...\n",
    " -> dans quel ordre de priorité doit on faire un tri multi-critères ?\n",
    " - dans un deuxième temps on fera le travail complet avec les conversions ...(pour vérifier que cela fonctionne, on remplacera le '05' minutes du vol Dublin par '5')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Dublin', 'heure': '20', 'minute': '05', 'num': 'BA409', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Munich', 'heure': '21', 'minute': '18', 'num': 'GA215', 'compagnie': 'GERMAN AIRWINGS'}]\n",
    "\n",
    "# définition des fonctions pour le paramètre 'key' :\n",
    "\n",
    "\n",
    "# compléter le code de tri:\n",
    "\n",
    "\n",
    "# afficher le résultat :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarque : on peut économiser des lignes de code en réalisant **le double tri dans une seule ligne d'instruction** :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Dublin', 'heure': '20', 'minute': '05', 'num': 'BA409', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Munich', 'heure': '21', 'minute': '18', 'num': 'GA215', 'compagnie': 'GERMAN AIRWINGS'}]\n",
    "\n",
    "# définition des fonctions pour le paramètre 'key' :\n",
    "\n",
    "\n",
    "# réaliser ici le tri en une seule ligne d'instruction (sur lequel des critères le tri est-il d'abord réalisé ?)\n",
    "\n",
    "# afficher le résultat :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réalisation du tri avec les conversions **str vers int**. \n",
    "\n",
    "On réalise les **conversions dans les fonctions** qui seront passées à l'argument key :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# on a remplacé le '05' minutes du vol Dublin par '5' pour vérifier que l'on fait bien un tri sur des\n",
    "# types eniters et non pas des chaînes de caractères...\n",
    "vols = [{'vol': 'Lisbonne', 'heure': '21', 'minute': '10', 'num': 'EJU7674', 'compagnie': 'EASYJET'},\n",
    "{'vol': 'Vienne', 'heure': '20', 'minute': '25', 'num': 'OS430', 'compagnie': 'AUSTRIAN AIRLINES'},\n",
    "{'vol': 'Londres', 'heure': '21', 'minute': '55', 'num': 'BA357', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Dublin', 'heure': '20', 'minute': '5', 'num': 'BA409', 'compagnie': 'BRITISH AIRWAYS'},\n",
    "{'vol': 'Munich', 'heure': '21', 'minute': '18', 'num': 'GA215', 'compagnie': 'GERMAN AIRWINGS'}]\n",
    "\n",
    "# définition des fonctions pour le paramètre 'key' ; on y réalisera les conversions nécessaires :\n",
    "\n",
    "\n",
    "# réaliser ici le tri en une seule ligne d'instruction (sur lequel des critères le tri est-il d'abord réalisé ?)\n",
    "\n",
    "# afficher le résultat :"
   ]
  }
 ],
 "metadata": {
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}