Notebook comparaison tri par insertion vs tri fusion

ComparaisonTriInsertionTriFusion.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Comparaison tri insertion, tri fusion\n",
    "\n",
    "Pour comparer la complexité en mombre d'opérations du tri par insertion et du tri fusion, nous allons appliquer chaque tri sur des listes dont la taille varie de 1 à 500. \\\n",
    "Pour chaque taille, nous allons générer aléatoirement 100 listes et nous allons consigner le nombre d'opérations moyen sur les 100 tris par insertion réalisés puis sur les 100 tris fusion réalisés. \\\n",
    "Nous allons utiliser les possibilités de Kotlin pour afficher les courbes fournissant le nombre d'opérations moyens d'opération en fonction de la taille des listes triées."
   ]
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 0. Import de librairies"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "// Ensures that the latest available library versions are used\n",
    "%useLatestDescriptors\n"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "// Imports the Kotlin DataFrame library\n",
    "%use dataframe\n",
    "\n",
    "// Imports the Kotlin Kandy library\n",
    "%use kandy"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 1. Collecte des données\n",
    "\n"
   ]
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import tp11.activite.bcd.ListeEntiers\n",
    "import tp11.activite.bcd.listeTrieeInstrumentee\n",
    "import tp11.activite.bcd.triParInsertionInstrumentee\n",
    "\n",
    "val TAILLE_MAX = 500\n",
    "\n",
    "val resultats = Array<IntArray>(TAILLE_MAX) { iTaille -> IntArray(3) { if ( it == 0) iTaille +1  else 0 } }\n",
    "\n",
    "for(iTaille in 1..TAILLE_MAX) {\n",
    "    var nbOperationsTriInsertion = 0\n",
    "    var nbOperationsTriFusion = 0\n",
    "    for(jNbTableaux in 1..100) {\n",
    "        val tab = IntArray(iTaille) { (-10_000..10_000).random() }\n",
    "        // Tri par instertion\n",
    "        val listeTriInsertion = ListeEntiers(tab)\n",
    "        nbOperationsTriInsertion += listeTriInsertion.triParInsertionInstrumentee()\n",
    "        // Tri fusion\n",
    "        val listeTriFusion = ListeEntiers(tab)\n",
    "        nbOperationsTriFusion +=listeTriFusion.listeTrieeInstrumentee().second\n",
    "    }\n",
    "    resultats[iTaille-1][1] = nbOperationsTriInsertion / 100    // moyenne du nombre d'opérations pour tri par insertion\n",
    "    resultats[iTaille-1][2] = nbOperationsTriFusion / 100       // moyenne du nombre d'opérations pour tri fuion\n",
    "}"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "*Encode en Json pour pourvoir utiliser un dataframe*"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import kotlinx.serialization.SerializationStrategy\n",
    "import kotlinx.serialization.json.Json\n",
    "\n",
    "val resultatsAsJsonString = Json.encodeToString(resultats)\n"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "*Chargement du Json dans un dataframe*"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "val dataFrame = DataFrame.readJsonStr(resultatsAsJsonString, header = listOf(\"Taille\", \"Insertion\", \"Fusion\"))\n",
    "dataFrame.head(5)"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": "dataFrame.tail(5)",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 2. Visualisation"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "dataFrame.plot {\n",
    "    x(Taille)\n",
    "    line {\n",
    "        y(Insertion)\n",
    "        color = Color.RED\n",
    "        width = 1.5\n",
    "    }\n",
    "    line {\n",
    "        y(Fusion)\n",
    "        color = Color.BLUE\n",
    "        width = 1.5\n",
    "    }\n",
    "    layout {\n",
    "        size = 1000 to 450\n",
    "        title = \"Comparaison tri par insertion (en rouge) vs tri fusion (en bleu)\"\n",
    "        xAxisLabel = \"Taille de la liste\"\n",
    "        yAxisLabel = \"Nombre moyen d'opérations\"\n",
    "    }\n",
    "}"
   ],
   "outputs": [],
   "execution_count": null
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Kotlin",
   "language": "kotlin",
   "name": "kotlin"
  },
  "language_info": {
   "name": "kotlin",
   "version": "2.2.20-Beta2",
   "mimetype": "text/x-kotlin",
   "file_extension": ".kt",
   "pygments_lexer": "kotlin",
   "codemirror_mode": "text/x-kotlin",
   "nbconvert_exporter": ""
  },
  "ktnbPluginMetadata": {
   "projectDependencies": [
    "TP-11P-Algorithmes-Tri"
   ],
   "projectLibraries": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}