Algorithmique 1 / Algorithmes de recherche et de tri

Voici un programme Python qui permet d'effectuer la recherche d'un nombre entier secret avec la méthode par balayage.

$\color{black}{\boxed{\scriptstyle{\textit{from random import *}\\
\textit{def ResultatEssai(essai,nombre_secret):}\\
\quad \textit{if essai < nombre_secret:}\\
\qquad \textit{return -1}\\
\quad \textit{elif essai == nombre_secret:}\\
\qquad \textit{return 0}\\
\quad \textit{return 1}\\
\quad\\
\textit{def recherche_pa_balayage(nombre_secret):}\\
\quad \textit{for i in range(1,101):}\\
\qquad\textit{if ResultatEssai(i,nombre_secret) ==0:}\\
\quad \qquad\textit{return i}\\
\quad \qquad\textit{nombre_secret = randint(1,101)}\\
\quad \qquad\textit{print(recherche_par_balayage(nombre_secret))}}}}$

La fonction Python nommée $\quad \textit{ResultatEssai(essai,nombre_secret)}$ retourne :

• $-1$ si le nombre essai est strictement inférieur au nombre secret
  
• $0$ si le nombre essai est égal au nombre secret
  
• $1$ si le nombre essai est strictement supérieur au nombre secret

La fonction Python recherche_par_balayage(nombre_secret) effectue la recherche d’un nombre secret avec une méthode par balayage et retourne le nombre de tentatives.

Voici un programme Python qui permet d'effectuer la recherche d'un nombre entier secret avec la méthode par dichotomie.

$\color{black}{\boxed{\scriptstyle{\textit{def ResultatEssai(essai,nombre_secret):}\\
\quad\textit{if essai < nombre_secret:}\\
\qquad \textit{return - 1}\\
\quad \textit{elif essai == nombre_secret:}\\
\qquad\textit{return 0}\\
\quad \textit{return 1}\\
\quad \\
\textit{def recherche_par_dichotomie(nombre_secret):}\\
\quad \textit{nb_tentatives = 0}\\
\quad \textit{trouve = False}\\
\quad \textit{essai = 50}\\
\quad \textit{inf = 1}\\
\quad \textit{sup = 100}\\
\quad \textit{while not(trouve):}\\
\qquad \textit{essai = int(inf + sup)/2)}\\
\qquad \textit{nb_tentatives += 1}\\
\qquad \textit{res = ResultatEssai(essai, nombre_secret)}\\
\qquad \textit{if res < 0:}\\
\qquad \quad \textit{inf = essai}\\
\qquad \textit{elif res == 0:}\\
\qquad \quad \textit{trouve = True}\\
\qquad \textit{else:}\\
\quad\qquad \textit{sup = essai}\\
\quad \textit{return nb_tentatives}\\
\quad\\
\textit{nombre_secret = randint(1,101)}\\
\textit{print(recherche_par_dichotomie(nombre_secret))}}}}$

Le programme par balayage effectue au maximum $100$ étapes ($100$ appels à la fonction ResultatEssai).

Le programme par dichotomie effectue au maximum $7$ étapes (car $26 < 100$ et $27 > 100$).

Si la taille de l’échantillon à analyser est $\rm N$, le nombre maximum d’étapes pour :

• L’algorithme de balayage est $\rm N$ ;
• L’algorithme de dichotomie est $\rm E \displaystyle \left(\frac{\ln N}{\ln 2}\right)+1$ désigne la fonction partie entière et $\ln()$ la fonction logarithme népérien).
  On peut montrer que le nombre moyen d’étapes pour rechercher un entier compris entre 1 et N avec : 
• La méthode par balayage est une fonction affine de $\rm N$ ;
  
• La méthode par dichotomie est une fonction affine du logarithme népérien de $\rm N$.
  

On visualise avec ce graphique le fait que l'algorithme de recherche par dichotomie est en moyenne beaucoup plus efficace que celui par balayage.

Un algorithme de tri permet de trier des données numériques ou alphabétiques.
Nous traiterons ici des données numériques stockées dans un tableau à une dimension.

Voici un programme Python qui implémente une fonction nommée tri_liste_non_en_place(liste) qui permet de trier par ordre décroissant la liste de nombres nommée "liste" à l'aide de deux autres listes "nliste" et "bliste".

$\color{black}{\boxed{\scriptstyle{\textit{from random import *}\\
\text{def tri_liste_non_en_place(liste):}\\
\quad\text{nliste : [0 for i in range(len(liste))]}\\
\quad\text{bliste = [False for i in range(len(liste))]}\\
\quad\text{for i in range(len(liste)):}\\
\qquad\text{max = -1}\\
\qquad\text{for j in range(len(liste)):}\\
\qquad \quad\text{if not(bliste[j]) and (max == -1 or liste[j] > max):}\\
\qquad \qquad \text{max = liste[j]}\\
\qquad \qquad\text{ind_max = j}\\
\qquad\text{nliste[i] = max}\\
\qquad\text{bliste[ind_max] = True}\\
\quad \text{return nliste}\\
\quad \\
\text{liste = [randint(à,1000) for i in range(10)]}\\
\text{print("Liste non triée",liste)}\\
\text{print("Liste triée",tri_liste_non_en_place(liste))}}}}$

Exemple d'exécution :

$\color{black}{\boxed{\scriptstyle{\text{Liste non triée [728, 144, 564, 819, 130, 886, 801, 130, 900, 568]}\\
\text{Liste triée [900, 886, 819, 801, 728, 568, 564, 144, 130, 130]}}}}$

Il est possible de trier les données à partir d’un seul tableau.
On dit alors qu’on effectue un tri sur place.
Il existe plusieurs algorithmes de tri en place qui ont des efficacités différentes.
Nous allons en étudier plusieurs.

a) Tri par insertion

Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C'est le tri que la plupart des personnes utilisent naturellement pour trier des cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.

Voici un algorithme de tri par insertion en pseudo-code :

$\color{blue}{\text{procédure tri_insertion (tableau T, entier n)}\\
\qquad \text{pour i de 1 à n-1}\\
\qquad \quad \rm x \leftarrow T[i]\\
\qquad \quad \rm j \leftarrow i\\
\qquad \quad \text{tant que j > 0 et T[j - 1] > x}\\
\qquad \qquad \rm T[j] \leftarrow T[j - 1]\\
\qquad \qquad \rm j \leftarrow j - 1\\
\qquad \quad\text{fin tant que}\\
\qquad \quad \rm T[j]\leftarrow x\\
\qquad \text{fin pour}\\
\quad\text{fin procédure}}$

Les éléments du tableau T sont numérotés de 0 à n – 1.

b) Complexité du tri par insertion

On montre (avec des maths !!) qu’en moyenne le nombre de boucles effectuées pour un tableau de taille n est $\displaystyle {\rm \frac{n^2}{4}}$

c) Des algorithmes de tri plus efficaces

Il existe d'autres algorithmes de tri :

• Tri à bulles (bubble sort)
  
• Tri par sélection (selection sort)
• Tri fusion (merge sort)
• Tri rapide (quick sort)
  

d) Complexité des algorithmes de tri

On trouve la complexité des algorithmes de tri dans le tableau suivant :

\[\begin{array}{|l|l|}
\hline
 & \color{blue}{\text{Complexité en moyenne}}\\
\color{blue}{\text{Méthode de tri}}&  \color{blue}{\text{pour un tableau de taille}}\\
&  \color{blue}{\rm N.}\\
\hline
\text{Tri par insertion} & \rm N^2\\
\hline
\text{Tri par sélection} & \rm N^2\\
\hline
\text{Tri à bulles} & \rm N^2\\
\hline
\text{Tri fusion} & \rm N \times log(N)\\
\hline
\text{Tri rapide} & \rm N \times log(N)\\
\hline
\end{array}\]

Les algorithmes les plus efficaces en moyenne sont ceux de tri par fusion ou de tri rapide.