{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4729fb96",
   "metadata": {},
   "source": [
    "# Algorithmes de tri sur les tableaux\n",
    "\n",
    "Le module `utils`, founi avec les notebooks, définit le type `IntArray` et des fonctions de création de tableaux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85e0de92",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1031d77c",
   "metadata": {},
   "source": [
    "Pour mettre en ouevre les algorithmes de tri, on utilisera la fonction `swapArray` ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce01a574",
   "metadata": {},
   "outputs": [],
   "source": [
    "def swapArray(t: IntArray, i: int, j: int) -> None:\n",
    "    \"\"\" Swaps values t[i] and t[j], assuming i and j are valid positions in t \"\"\"\n",
    "    x: int = t[i]\n",
    "    t[i] = t[j]\n",
    "    t[j] = x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "248ab76d",
   "metadata": {},
   "source": [
    "## Tri à bulle\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:**\n",
    "- on commence par placer la plus grande valeur en dernière position\n",
    "  - on part de `t[0]`, et à chaque fois que `t[i+1] < t[i]` on les échange\n",
    "  - ainsi, la plus grande valeur va \"remonter\" en dernière position\n",
    "- puis on procède de même avec la deuxième plus grande valeur\n",
    "  - elle remontera en avant dernière position\n",
    "- et ainsi de suite"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01bdc988",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubbleSort(t: IntArray):\n",
    "    for i in range(t.size - 1, 0, -1):\n",
    "        for j in range(0, i):\n",
    "            if t[j+1] < t[j]:\n",
    "                swapArray(t, j, j+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17102349",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction bubbleSort\n",
    "\n",
    "for size in range(1,20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    bubbleSort(t)\n",
    "    assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bab78db5",
   "metadata": {},
   "source": [
    "Le tri à bulle est de complexité $\\Omicron(n^2)$ au pire (tableau trié décroissant) et au mieux (tableau trié croissant). On peut améliorer la complexité au mieux en détectant les échanges de valeurs. Si aucune valeur n'a été échangée, on peut en conclure que le tableau est trié."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af2e471d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubbleSortOpt(t: IntArray):\n",
    "    swapped: bool = False\n",
    "    for i in range(t.size - 1, 0, -1):\n",
    "        for j in range(0, i):\n",
    "            if t[j+1] < t[j]:\n",
    "                swapArray(t, j, j+1)\n",
    "                swapped = True\n",
    "        if not swapped:\n",
    "            return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d04431d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction bubbleSortOpt\n",
    "\n",
    "for size in range(1,20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    bubbleSortOpt(t)\n",
    "    assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "955501cc",
   "metadata": {},
   "source": [
    "## Tri par sélection (ou extraction)\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:**\n",
    "- supposons que les valeurs `t[0]`, ..., `t[i-1]` sont triées, et inférieures ou égales aux valeurs `t[i]`, ..., `t[t.size-1]`\n",
    "- on calcule l'index `j` du minimum de `t` à partir de l'indice `i`\n",
    "- on échange `t[i]` et `t[j]`\n",
    "\n",
    "1. On fournit la fonction `argmin` ci-dessous. Que calcule-t-elle?\n",
    "2. Mettre en oeuvre la fonction `selectionSort`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4176a799",
   "metadata": {},
   "outputs": [],
   "source": [
    "def argmin(t: IntArray, i: int) -> int:\n",
    "    assert i < t.size\n",
    "    imin = i\n",
    "    for k in range(i+1, t.size):\n",
    "        if t[k] < t[imin]:\n",
    "            imin = k\n",
    "    return imin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba8d4324",
   "metadata": {},
   "outputs": [],
   "source": [
    "def selectionSort(t: IntArray):\n",
    "    for i in range(t.size-1):\n",
    "        imin = argmin(t, i)\n",
    "        swapArray(t, i, imin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30f6e920",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction selectionSort\n",
    "\n",
    "for size in range(1,20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    selectionSort(t)\n",
    "    assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97d665ee",
   "metadata": {},
   "source": [
    "## Tri par insertion\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:**\n",
    "- supposons que les valeurs `t[0]`, ..., `t[i-1]` sont triées\n",
    "- on \"descend\" `t[i]` à sa place par échanges successifs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1743b680",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertionSort(t: IntArray):\n",
    "    for i in range(1, t.size):\n",
    "        for j in range(i, 0, -1):\n",
    "            if t[j] >= t[j-1]:\n",
    "                break;\n",
    "            swapArray(t, j, j-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f445e679",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction insertionSort\n",
    "\n",
    "for size in range(1,20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    insertionSort(t)\n",
    "    assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f743ee9",
   "metadata": {},
   "source": [
    "## Tri fusion naïf\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:** on utilise l'approche \"diviser pour régner\"\n",
    "- à partir de `t`, on *divise* `t` en deux tableaux `a = t[0..middle]` et `b=[middle..t.size]` où `middle` est l'indice au milieu de `t`\n",
    "- on *trie récursivement* les tableaux `a` et `b`\n",
    "- puis on *fusionne* `a` et `b` en maintenant le tri, et on copie le résultat dans `t`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "595b9097",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sorted_arrays(a: IntArray, b: IntArray) -> IntArray:\n",
    "    \"\"\" Retourne le tableau obtenu par fusion des tableaux triés a et b \"\"\"\n",
    "    c = newIntArray(a.size + b.size)\n",
    "\n",
    "    i: int = 0  # index in array a\n",
    "    j: int = 0  # index in array b\n",
    "\n",
    "    # invariants:\n",
    "    # - les éléments de c[0..k] sont ceux de a[0..i] et b[0..j]\n",
    "    # - c[0..k] est trié\n",
    "    for k in range(c.size):\n",
    "        if i < a.size and (j >= b.size or a[i] <= b[j]):\n",
    "            c[k] = a[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            c[k] = b[j]\n",
    "            j += 1\n",
    "\n",
    "    return c\n",
    "\n",
    "def naiveMergeSort(t: IntArray) -> IntArray:\n",
    "    if t.size <= 1:\n",
    "        return t\n",
    "    middle = t.size // 2\n",
    "    a = cloneIntArray(t[:middle])\n",
    "    b = cloneIntArray(t[middle:])\n",
    "    a = naiveMergeSort(a)\n",
    "    b = naiveMergeSort(b)\n",
    "    return merge_sorted_arrays(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "424eb204",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction naiveMergeSort\n",
    "\n",
    "for size in range(1, 20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    actual = naiveMergeSort(t)\n",
    "    assert np.array_equal(actual, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d27c696",
   "metadata": {},
   "source": [
    "## Tri fusion (merge sort)\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:** on se base sur une approche \"diviser pour régner\". Étant donné `t`, et deux bornes `l` et `u`:\n",
    "- on *divise* `t[l..u]` en `t[l..p]` et `t[p..u]` où `p` est au milieu de `l` et `u`\n",
    "- on trie *récursivement* `t[l..p]` et `t[p..u]`\n",
    "- puis on *fusionne* les tableaux triés dans `t`\n",
    "Pour faciliter la fusion, l'algorithme utilise un second tableau `a` dans lequel in stocke les sous-tableaux triés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1da7ee8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSorted(t: IntArray, begin: int, middle: int, end: int, a: IntArray) -> None:\n",
    "    \"\"\" Merges the two sorted parts t[begin..middle] and t[middle..end] into a[begin..end] \"\"\"\n",
    "    i: int = begin;\n",
    "    j: int = middle;\n",
    "    for k in range(begin, end):\n",
    "        if i < middle and (j >= end or t[i] <= t[j]):\n",
    "            a[k] = t[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            a[k] = t[j]\n",
    "            j += 1\n",
    "\n",
    "def recMergeSort(t: IntArray, begin: int, end: int, a: IntArray) -> None:\n",
    "    \"\"\" Splits a[begin..end] into two equal parts, sorts them recursively, and merge them into t \"\"\"\n",
    "    if end - begin <= 1:\n",
    "        return\n",
    "\n",
    "    # Swap final and working arrays at each level\n",
    "    middle: int = (begin + end) // 2\n",
    "    recMergeSort(a, begin, middle, t)\n",
    "    recMergeSort(a, middle, end, t)\n",
    "\n",
    "    mergeSorted(a, begin, middle, end, t)\n",
    "\n",
    "def mergeSort(t: IntArray) -> None:\n",
    "    \"\"\" Sorts array t using top-down merge sort \"\"\"\n",
    "    a = cloneIntArray(t)\n",
    "    recMergeSort(t, 0, t.size, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a1ff4fe8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction mergeSort\n",
    "\n",
    "for size in range(1, 20):\n",
    "    t = newRandomIntArray(size, 0, size)\n",
    "    expected = sorted(cloneIntArray(t))\n",
    "    mergeSort(t)\n",
    "    assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b40510ab",
   "metadata": {},
   "source": [
    "## Tri rapide (quick sort)\n",
    "\n",
    "Trier un tableau d'entiers `t` par ordre croissant\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `t` est trié, et il contient les mêmes valeurs et en même nombre\n",
    "\n",
    "**Principe:** on se base sur une approche \"diviser pour régner\". Étant donné `t`, et deux bornes `l` et `u`:\n",
    "- on choisit un élément pivot `t[p]` et on *partitionne* `t` en deux: d'une part les éléments plus petits que `t[p]`, et d'autre part ceux plus grands que `t[p]` (diviser)\n",
    "- on trie alors *récursivement* chacune des deux parties\n",
    "- puis on les rassemble\n",
    "\n",
    "**NB:**\n",
    "- lors de la partition, les deux parties obtenues ne sont *oas triées*.\n",
    "- le choix du pivot `p` est crucial pour obtenir une bonne complexité quand `t` est déjà (quasi-)trié. Il existe plusieurs stratégies: en pratique, le milieu ou un élément au hasard, sont de bons choix.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f68d25c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(t: IntArray, begin: int, end: int, pivot: int) -> Tuple[int, int]:\n",
    "    \"\"\" Partitions t[begin..end] around pivot. The returned indices (lt, gt) are such that: t[begin..lt] contains elements less than pivot, t[lt..gt+1] contains elements equal to pivot, and t[gt+1..end] contains elements greater than pivot \"\"\"\n",
    "\n",
    "    lt = begin\n",
    "    gt = end - 1\n",
    "    i = begin\n",
    "    \n",
    "    # invariants:\n",
    "    # - les entiers de t[begin..lt] sont < pivot\n",
    "    # - les entiers de t[lt..i] sont = pivot\n",
    "    # - les entiers de t[i..gt+1] doivent encore être placés\n",
    "    # - les entiers de t[gt+1..end] sont > pivot\n",
    "    while i <= gt:\n",
    "        if t[i] < pivot:\n",
    "            swapArray(t, i, lt)\n",
    "            lt += 1\n",
    "            i += 1\n",
    "        elif t[i] > pivot:\n",
    "            swapArray(t, i, gt)\n",
    "            gt -= 1\n",
    "        else: # A[i] == pivot\n",
    "            i += 1\n",
    "\n",
    "    return lt, gt + 1\n",
    "\n",
    "def recQuickSort(t: IntArray, begin: int, end: int) -> None:\n",
    "    \"\"\" Sorts t[begin..end] recursively using quick sort \"\"\"\n",
    "    #if begin >= 0 and begin < end:\n",
    "    if end - begin <= 1:\n",
    "        return\n",
    "    # pivot = t[(begin + end) // 2]\n",
    "    pivot = t[random.randint(begin, end-1)]\n",
    "    lt, gt = partition(t, begin, end, pivot)\n",
    "    recQuickSort(t, begin, lt)\n",
    "    recQuickSort(t, gt, end)\n",
    "\n",
    "def quickSort(t: IntArray) -> None:\n",
    "    \"\"\" Sorts array t using quick sort \"\"\"\n",
    "    recQuickSort(t, 0, t.size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f89d096",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction quickSort\n",
    "\n",
    "for size in range(1, 20):\n",
    "   t = newRandomIntArray(size, 0, size)\n",
    "   expected = sorted(cloneIntArray(t))\n",
    "   quickSort(t)\n",
    "   assert np.array_equal(t, expected)\n",
    "print(\"OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1661bf2c",
   "metadata": {},
   "source": [
    "## Comparaison expérimentale des algorithmes de tri"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d9880de",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Mesure des temps de calcul\n",
    "\n",
    "# Taille max du tableau et valeur max de x\n",
    "MAX_SIZE = 2000\n",
    "\n",
    "# Nombre d'expériences\n",
    "SAMPLE_SIZE = 100\n",
    "\n",
    "sizes = np.empty(SAMPLE_SIZE)\n",
    "times_sel = np.empty(SAMPLE_SIZE)\n",
    "times_ins = np.empty(SAMPLE_SIZE)\n",
    "times_bub = np.empty(SAMPLE_SIZE)\n",
    "times_naive = np.empty(SAMPLE_SIZE)\n",
    "times_mrg = np.empty(SAMPLE_SIZE)\n",
    "times_qck = np.empty(SAMPLE_SIZE)\n",
    "\n",
    "for i in range(SAMPLE_SIZE):\n",
    "    size = random.randint(1, MAX_SIZE + 1)\n",
    "    t_sel = newRandomIntArray(size, 0, size)\n",
    "    t_ins = cloneIntArray(t_sel)\n",
    "    t_bub = cloneIntArray(t_sel)\n",
    "    t_naive = cloneIntArray(t_sel)\n",
    "    t_mrg = cloneIntArray(t_sel)\n",
    "    t_qck = cloneIntArray(t_sel)\n",
    "    sizes[i] = size\n",
    "    times_sel[i] = timeit.timeit(lambda: selectionSort(t_sel), number=2)\n",
    "    times_ins[i] = timeit.timeit(lambda: insertionSort(t_ins), number=2)\n",
    "    times_bub[i] = timeit.timeit(lambda: bubbleSort(t_bub), number=2)\n",
    "    times_naive[i] = timeit.timeit(lambda: naiveMergeSort(t_naive), number=2)\n",
    "    times_mrg[i] = timeit.timeit(lambda: mergeSort(t_mrg), number=2)\n",
    "    times_qck[i] = timeit.timeit(lambda: quickSort(t_qck), number=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "99bc9ecd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Graphe des temps d'exécution\n",
    "\n",
    "# All algorithms\n",
    "fig, axs = plt.subplots(figsize=(12, 8))\n",
    "\n",
    "axs.scatter(sizes, times_ins, label=\"insertion\", alpha=0.2, c='cyan')\n",
    "axs.scatter(sizes, times_sel, label=\"sélection\", alpha=0.2, c='blue')\n",
    "axs.scatter(sizes, times_bub, label=\"bulle\", alpha=0.2, c='purple')\n",
    "axs.scatter(sizes, times_naive, label=\"fusion naïf\", alpha=0.2, c='green')\n",
    "axs.scatter(sizes, times_mrg, label=\"fusion\", alpha=0.2, c='orange')\n",
    "axs.scatter(sizes, times_qck, label=\"quicksort\", alpha=0.2, c='red')\n",
    "axs.legend()\n",
    "axs.set_xlabel(\"taille n\")\n",
    "axs.set_ylabel(\"temps (s.)\")\n",
    "\n",
    "# O(n.log(n)) algorithms only\n",
    "fig2, axs2 = plt.subplots(figsize=(12, 8))\n",
    "\n",
    "nlogn_10m6 = [10**-6 * n * np.log2(n) for n in sizes]\n",
    "nlogn_10m7 = [10**-7 * n * np.log2(n) for n in sizes]\n",
    "\n",
    "axs2.scatter(sizes, nlogn_10m6, label=\"10**(-6).n.log(n)\", alpha=0.2, c='black')\n",
    "axs2.scatter(sizes, nlogn_10m7, label=\"10**(-7).n.log(n)\", alpha=0.2, c='gray')\n",
    "axs2.scatter(sizes, times_naive, label=\"fusion naïf\", alpha=0.2, c='green')\n",
    "axs2.scatter(sizes, times_mrg, label=\"fusion\", alpha=0.2, c='orange')\n",
    "axs2.scatter(sizes, times_qck, label=\"quicksort\", alpha=0.2, c='red')\n",
    "axs2.legend()\n",
    "axs2.set_xlabel(\"taille n\")\n",
    "axs2.set_ylabel(\"temps (s)\")\n",
    "\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pyvenv-3.14 (3.14.8)",
   "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.14.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}