3. Algorithmique 4 - Déplacement de zéro

3.1. Méthodes

On rappelle que le but de l'exercice est de déplacer dans un tableau d'entiers, les éléments de valeur 0 au début du tableau.

On définit deux méthodes pour déplacer ces éléments :

méthode 1 : on déplace les éléments 0 au début du tableau quand on en trouve, l'inconvénient est que l'on déplace beaucoup de valeurs quand il n'y a que des 0
méthode 2 : tant qu'on a des 0 au début du tableau on passe à l'indice suivant, puis on continu avec la méthode 1

3.1.1. Méthode 1

On utilise deux indices :

i est l'indice qui permet de parcourir le tableau, il varie de 1 à $N$, si $N$ est la taille du tableau
i0 est l'indice où on place les éléments zéro, initialement il est égal à 1

dès que l'on trouve un élément égal à zéro, on le place à l'indice i0, puis on incrémente i0.

CODE
methode_1.algo

proc put_zero_at_beginning( t is array[1..N] of int)
 
    variable i, i0 are int
 
    i0 = 1
    for i in range(1,N) do
        if t[i] = 0 then
            swap t[i] with t[i0]
            i0 = i0 + 1
        end if
    end for
 
end proc
 

L'inconvénient majeur de cette méthode est qu'elle échange t[i] avec t[i0] avec i = i0 lorsqu'on a des éléments zéro au début du tableau.

3.1.2. Méthode 2

On modifie la méthode précédente pour chercher le premier élément qui n'est pas un zéro :

CODE
methode_2.algo

proc put_zero_at_beginning( t is array[1..N] of int)
 
    variable i, i0 are int
 
    i = 1
    i0 = 1
    
    while i <= N and t[i] = 0 do
        i = i + 1
    end while
    
    while i <= N do
        if t[i] = 0 then
            swap t[i] with t[i0]
            i0 = i0 + 1
        end if
    end for
 
end proc
 

3.2. Résultats

3.2.1. Résultats sur un tableau de 100 éléments

Voici quelques résultats avec un tableau de 100 éléments dont un tiers des éléments sont des 0.

On reporte le nombre d'affectations, de comparaisons et d'incrémentations, ainsi que le total de ces 3 opérations.

Résultats en fonction du remplissage et de la méthode
Remplissage	Méthode	Affectations	Comparaisons	Incrémentations	Total
Aléatoire	Méthode 1	99	100	33	232
Aléatoire	Méthode 2	99	167	33	299
Que des 0	Méthode 1	300	100	100	500
Que des 0	Méthode 2	0	100	100	200
Sans 0	Méthode 1	0	100	0	100
Sans 0	Méthode 2	0	100	0	101

On remarque que dans le cas ou le tableau ne comprend que des zéro, la méthode 2 engendre moins de calculs (200) alors que la méthode 1 en engendre 500.

3.2.2. Test de performance

A présent, un test de performance avec un tableau de 100 millions d'éléments dont un tiers des éléments sont des 0. Le processeur utilisé est un AMD Ryzen 5 5600G.

Résultats en fonction du remplissage et de la méthode
Remplissage	Méthode	Affectations	Comparaisons	Incrémentations	Total	Temps (s)
Aléatoire	Méthode 1	99999999	100000000	33333333	233333332	0.240853
Aléatoire	Méthode 2	99999999	166666667	33333333	299999999	0.236566
Que des 0	Méthode 1	300000000	100000000	100000000	500000000	0.0919376
Que des 0	Méthode 2	0	100000000	100000000	200000000	0.0367108
Sans 0	Méthode 1	0	100000000	0	100000000	0.029863
Sans 0	Méthode 2	0	100000001	0	100000001	0.027379