{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Description du problème" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On s'intéresse au problème du tri d'une liste.\n", "\n", "Plus précisément, on dispose d'une liste L de n éléments comparables, et on veut rendre la liste des éléments de L dans l'ordre croissant (il est facile d'adapter les idées pour obtenir l'ordre décroissant)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def tri_naif(L):\n", " \"\"\"\n", " L'idée est d'aller chercher le plus petit élément de L\n", " puis de le placer en première position.\n", " On recommencer à partir de la position 2.\n", " \"\"\"\n", " n = len(L)\n", " for i in range(0, n-1):\n", " # on cherche le minimum de L[i:]\n", " m = i # indice courant du minimum\n", " for j in range(i, n):\n", " if L[j] < L[m]:\n", " m = j\n", " # le minimum de L[i:] est à la position m,\n", " # plaçons le au début, c'est à dire en i\n", " L[i], L[m] = L[m], L[i]\n", " return L" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-1, 2, 4, 5, 6]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = [-1,5,2,4,6]; tri_naif(L)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['a', 'e', 'i', 'o', 'p', 'r', 't', 'u', 'y', 'z']" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = list(\"azertyuiop\")\n", "tri_naif(L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Tri par insertion." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Description de l'algorithme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le principe est simple.\n", "