Samedi après midi, à l’heure de la sieste pour certains, nous discutions avec Magali, Jean Baptiste et Florent des machines qui pouvaient trier les cartes, de là, la discussion a dévié sur les algorithmes de tri, et sur la difficulté d’expliquer l’importance de la vitesse d’un algorithme, ou plus généralement, la vitesse de convergence. Bref, avant de parler de vitesse de convergence en statistique – ou peut être avant sur les méthodes de calcul d’intégrale (ou d’espérance) – je voulais faire un petit billet rapide sur les algorithmes de tri. Je commence par des choses simples. De mémoire c’est des choses que je me souviens avoir vu au lycée dans les années 90, dans les cours d’informatique… Mais l’exemple peut être intéressant pour comprendre la différence, par exemple, entre ,  et .
Le premier algorithme est appelé tri à bulles. C’est probablement l’algorithme le plus simple, et sa vitesse est en . On va balayer autant de fois la base que l’on a d’observations, et à chaque passage, on récupère le maximum (ou le minimum, peu importe). L’algorithme ressemble à ça,

> n=25; s=1
> X=sample(1:n,size=n,replace=FALSE)
>          for(i in 1:(n-1)){
+          for(j in 1:(n-1)){
+          s=s+1
+          if(X[j] > X[j + 1]){X[c(j,j+1)]=X[c(j+1,j)]}
+          }}

Si on l’implémente, voilà ce que ça donne (tous les graphiques partent de la même permutation initiale, et tous contiennent autant d’images, de l’ordre de )

Bref, un algorithme en .Bon, j’ai été un peu brutal dans mon algorithme. En fait, on voit que les derniers points sont rapidement bien classés, donc inutile que la seconde boucle aille jusqu’au bout… on peut donc faire du , en faisant

+          for(j in 1:(n-i)){

Bref, la constante dans les peut être relativement importante comme on le voit ici.

Mais on peut faire  mieux, voire beaucoup mieux comme on le verra ensuite.
Le second algorithme est le tri par insertion. C’est aussi un algorithme très simple:  on balaye l’ensemble en plaçant les valeurs rencontrées à leur place, un peu comme quand on tri ses cartes… L’algorithme est là aussi en . Ici l’algorithme converge un peu plus rapidement que le précédant, mais cela vient du fait que les données étaient partiellement ordonnées sur la fin. Autrement dit, un autre échantillon aurait pu donner autre chose… Mais généralement, c’est le cas.

>          for(i in 1:n){
+           x = X[i]
+          for(j in (i+1):2){
+          s=s+1
+         if(X[j - 1] < x){X[j] = X[j - 1];  j = j - 1;  X[j] = x}
+         }
+         }

(le tri est fait à l’envers ici…. mais c’est un détail).

Enfin, le tri fusion est un autre algorithme en . L’idée est de couper, de trier, puis de fusionner. L’idée étant que trier un tableau dont la première moitié des éléments sont ordonnés, et où la dernière moitié est ordonné doit être plus rapide que quand tout est dans le désordre. A chaque étape, l’algorithme est simple, on compare le minimum des deux listes, puis on le vire à l’étape suivante. Sous R, ça donne, quand on commence

> for(i in 0:(trunc(n/2)-1)){
+ Y=X[c(1,2)+2*i]
+ if(Y[1]>Y[2]){X[c(1,2)+2*i]=X[c(2,1)+2*i]}
+ }

Bref, en commençant par classer les paires (1,2) puis (3,4), etc, puis les listes (1,2) versus (3,4). Le code est alors de la forme

> k=4
> for(i in 0:(trunc(n/4)-1)){
+ Y=X[1:k+k*i]
+ Y1=c(Y[1:(k/2)],rep(999999,k/2));Y2=c(Y[(k/2+1):k],rep(999999,k/2));
+ for(j in 1:k+k*i){
+     X[j]=min(c(Y1[1],Y2[1]),na.rm=TRUE)
+    if(X[j]==Y1[1]){Y1=Y1[
-1]}
+    if(X[j]==Y2[1]){Y2=Y2[-1]}
+ }}

(avec une petite correction pour le dernier bloc, qui ne compare pas forcément un bloc de taille 2 contre un autre de taille 2 (mais l’adaptation du code est infime). Puis on continue avec (1,2,3,4) versus (5,6,7,8), c’est relativement rapide de tout classer, comme le montre l’animation ci-dessous.

Il existe de très nombreux autres algorithmes de tri, le but étant de monter qu’un algorithme en  va effectivement beaucoup plus vite qu’un algorithme en . J’ai tout fait ici en R, mais pour les adeptes d’autres langages, il existe plein de code en ligne, ici par exemple. Pour conclure, le graphique ci-dessous montre les différences entre les vitesses de convergence en  (en noir), en  (en rouge) et en  (en bleu),

La suite sur la convergence des méthodes de monte carlo, puis des théorèmes limites en stats….