CHAPITRE 8 : LES TABLEAUX : ALGORITHMES CLASSIQUES

Ce chapitre rassemble les algorithmes sur tableaux qui reviennent le plus souvent. Les connaitre par coeur fait gagner un temps considerable.

1. Recherche avec position

trouve <- FAUX;
i      <- 1;

TantQue(i <= N ET NON trouve) Faire

    Si(T[i] = x) Alors
        trouve <- VRAI;
    Sinon
        i <- i + 1;
    FinSi

FinTantQue

Si(trouve) Alors
    Ecrire("Trouve en position ", i);
Sinon
    Ecrire("Absent");
FinSi

Recherche de 20 dans [15, 9, 7, 20, 11] :

2. Maximum avec sa position

max       <- T[1];
indiceMax <- 1;

Pour i de 2 a N Faire

    Si(T[i] > max) Alors
        max       <- T[i];
        indiceMax <- i;
    FinSi

FinPour

3. Minimum et maximum en un seul parcours

Inutile de parcourir le tableau deux fois :

min <- T[1];
max <- T[1];

Pour i de 2 a N Faire

    Si(T[i] > max) Alors
        max <- T[i];
    FinSi

    Si(T[i] < min) Alors
        min <- T[i];
    FinSi

FinPour

4. Somme et comptage conditionnels

s  <- 0;
nb <- 0;

Pour i de 1 a N Faire

    Si(T[i] > 0) Alors
        s  <- s + T[i];
        nb <- nb + 1;
    FinSi

FinPour

5. Inverser un tableau

Avant :  3  5  8  10  15
Apres : 15 10  8   5   3

On utilise deux indices qui se rapprochent :

g <- 1;
d <- N;

TantQue(g < d) Faire

    temp <- T[g];
    T[g] <- T[d];
    T[d] <- temp;

    g <- g + 1;
    d <- d - 1;

FinTantQue

La variable temp est indispensable : sans elle, on ecrase une valeur avant de l'avoir sauvegardee.

6. Le tri a bulles

A chaque passage, les plus grandes valeurs remontent vers la fin du tableau : d'ou son nom.

Depart           :  8  3  6  1
Premier passage  :  3  6  1  8
Deuxieme passage :  3  1  6  8
Troisieme passage:  1  3  6  8

Le principe

Comparer deux cases voisines. Si elles sont mal ordonnees, les echanger. Repeter jusqu'a ce qu'aucun echange ne soit necessaire.

L'algorithme

permute <- VRAI;

TantQue(permute) Faire

    permute <- FAUX;

    Pour i de 1 a N-1 Faire

        Si(T[i] > T[i+1]) Alors

            temp   <- T[i];
            T[i]   <- T[i+1];
            T[i+1] <- temp;

            permute <- VRAI;

        FinSi

    FinPour

FinTantQue

C'est une version optimisee : le drapeau permute permet de s'arreter des que le tableau est trie, sans faire de passages inutiles.

Complexite

Dans le pire cas, le tri a bulles effectue environ N² comparaisons. Il convient donc aux petits tableaux ; sur de grandes quantites de donnees, d'autres tris sont preferables.

7. Fusionner deux tableaux

k <- 1;

Pour i de 1 a NA Faire
    C[k] <- A[i];
    k    <- k + 1;
FinPour

Pour j de 1 a NB Faire
    C[k] <- B[j];
    k    <- k + 1;
FinPour

L'indice k continue d'avancer d'un tableau a l'autre : c'est la cle.

8. Les tableaux a deux dimensions

Un tableau a deux dimensions est une matrice.

1 2 3
4 5 6
7 8 9

Var
    M : Tableau[1..L, 1..C] de entier;

Lecture et affichage

Pour i de 1 a L Faire
    Pour j de 1 a C Faire
        Lire(M[i,j]);
    FinPour
FinPour

Deux boucles imbriquees : la premiere parcourt les lignes, la seconde les colonnes.

Somme des elements

s <- 0;

Pour i de 1 a L Faire
    Pour j de 1 a C Faire
        s <- s + M[i,j];
    FinPour
FinPour

9. Les erreurs frequentes

• Acceder a une case inexistante
• Oublier d'initialiser max ou min
• Echanger deux valeurs sans variable temporaire
• Confondre l'indice et la valeur : i n'est pas T[i]

A retenir

• Un echange necessite toujours une variable temporaire
• Le tri a bulles compare les voisins et repete jusqu'a stabilite
• Sa complexite est de l'ordre de N²
• Une matrice se parcourt avec deux boucles imbriquees
• Preferez un seul parcours quand plusieurs calculs sont possibles ensemble