الجزء التاني cours d'algorithme pour TSDI

Algorithmes pour les figures géométriques
Algorithmes de base sur les tableaux
Parcours d'un tableau
Algorithme AfficheTableau (t : tableau ; n : entier)

{Affiche tous les éléments d'un tableau}

Variable i : entier

Début

Pour i := 1 à n faire

Afficher (t[i])

Fin Pour

Fin

Algorithme AfficheTableauEnHTML (t : tableau ; n : entier)

{Affiche les éléments d'un tableau sous forme de liste HTML}

Variable i : entier

Début

Afficher ("<ul>")

Pour i := 1 à n faire

Afficher ("<li>")

Afficher (t[i])

Afficher ("</li>")

Fin Pour

Afficher ("</ul>")

Fin

Recherche du plus grand élément d'un tableau
Algorithme Maximum (t : tableau d'entiers ; n : entier)

{Recherche l'élément le plus grand d'un tableau de taille n non nulle}

Variables i, max : entier

Début

max := t [0]

Pour i := 1 à n faire

Si (t[i] > max)

Alors max := t[i]

Fin si

Fin Pour

Afficher (max)

Fin



Déroulement du programme sur le tableau

4
2
5
1
3




i
Max

0
4

1
4

2
5

3
5

4
5


et l'algorithme affiche la valeur 5

Pour mesurer la complexité d'un algorithme, il faut tout d'abord désigner une ou plusieurs opérations élémentaires utilisées par l'algorithme. Dans le cas de la recherche du maximum d'un tableau, ces opérations pourront être :

· la comparaison entre le maximum connu et un élément du tableau ( t[i] > max ) ;

· l'affectation d'une valeur à la variable contenant le maximum ( max := t[0] et max := t[i] ).

Mesurer la complexité de l'algorithme revient alors à compter le nombre de fois où ces opérations sont effectuées par l'algorithme.

Ainsi, pour un tableau de taille n, l'algorithme Maximum effectue n-1 comparaisons.

Naturellement, nous le voyons avec l'algorithme Maximum et le nombre d'affectations qu'il effectue, la complexité peut varier avec les données fournies en entrée. Nous allons donc distinguer trois notions de complexité : au mieux, au pire et en moyenne.

· Le cas le plus favorable pour notre algorithme Maximum est le cas où le maximum du tableau se trouve en première position : la variable max prend cette valeur au début et n'en change plus ensuite. La complexité au mieux vaut donc 1.

· Au pire, le tableau est trié en ordre croissant et la variable max doit changer de valeur avec chaque case. La complexité au pire va donc n.

· La complexité en moyenne est plus difficile à calculer. Il ne s'agit pas comme on pourrait le penser de la moyenne des complexités au mieux et au pire. Nous pouvons observer que si nous choisissons un tableau au hasard, il est beaucoup plus probable d'avoir un tableau dont le maximum est en première place (cas le mieux) qu'un tableau complètement trié (cas le pire). Par conséquent, la complexité en moyenne est plus proche de 1 que de n et, en effet, il est possible de montrer que cette complexité en moyenne vaut log (n).

En résumé, nous avons pour la complexité de l'algorithme Maximum en nombre d'affectations sur un tableau de taille n :

au mieux
en moyenne
au pire

1
log (n)
n


Existence d'un élément dans un tableau
Algorithme Présent (e : entier ; t : tableau d'entiers ; n : entier)

{Indique si l'élément e est présent ou non dans le tableau t }

Variable i : entier

Début

i := 1;

Tant que (i <= n) et non (t[i] = e) faire

i := i+1

Fin tant que

Si (i>n)

Alors Afficher ("l'élément recherché n'est pas présent")

Sinon Afficher ("l'élément recherché a été découvert")

Fin si

Fin

Retour sur le codage binaire : utilisation d'un tableau
Nous supposons ici que le tableau est numéroté à partir de zéro et que la case d'indice 0 contient le bit de poids faible.

Algorithme BinaireVersDécimal (t : tableau de 0 et de 1 ; n : entier)

{Calcule la valeur décimale dénotée par un tableau de bits}

Variables i, val, puiss : entier

Début

val := 0;

puiss := 1;

Pour i := 0 à n-1 faire

val := val + puiss*t[i]

puiss := 2*puiss

Fin Pour

Afficher (val)

Fin

Algorithme DécimalVersBinaire (e : entier)

{Calcule le codage binaire d'un entier e en utilisant un tableau de bits}

Variable i : entier

t : tableau de 0 et de 1

Début

i := 0;

Tant que non(e = 0) faire

t[i] := e modulo 2

e := e div 2

i := i+1

Fin tant que

Affiche Tableau (t,i)

Fin

Algorithmes de tri de tableaux
Algorithme d'échange
Algorithme Echange (t : tableau d'entiers ; i, j : entiers)

{Echange le contenu des cases i et j dans le tableau t}

Variable Pro : entier

Début

Pro := t[i]

t [i] := t[j]

t [j] := pro

Fin

Principe du tri extraction
Aussi nommé tri sélection.

en utilisant l'algorithme Minimum

1. Extraire l'élément le plus petit du tableau à trier.

2. Echanger cette valeur minimale avec la première case du tableau à trier.

3. Trier le reste du tableau (le tableau initial sans la première case) de la même manière.

Tri à bulles
Algorithme Tri Bulles (t : tableau d'entiers ; n : entier)

{Trie par ordre croissant le tableau t contenant n éléments}

Variables i, j : entier

Début

Pour i := 1 à n-1 faire

Pour j := 1 à n-i faire

Si t[j] > t [j+1]

Alors Echange (t, j, j+1)

Fin Si

Fin Pour

Fin Pour

Fin

Principe du tri rapide
1. Choisir un élément du tableau, élément que l'on nomme ensuite pivot.

2. Placer le pivot à sa position finale dans le tableau : les éléments plus petits que lui sont à sa gauche, les plus grands à sa droite.

3. Trier, toujours à l'aide de cet algorithme, les sous tableaux à gauche et à droite du tableau.

Pour que cette méthode soit la plus efficace possible, il faut que le pivot coupe le tableau en deux sous tableaux de tailles comparables.

Ainsi, si l'on choisit à chaque le plus petit élément du tableau comme pivot, on se retrouve dans le cas de l'algorithme de tri par extraction : la taille du tableau de diminue que d'un à chaque alors que le but est de diviser cette taille par deux.

Cependant, bien choisir le pivot peut être coûteux en terme de complexité.

Aussi on suppose que le tableau arrive dans un ordre aléatoire et on se contente de prendre le premier élément comme pivot.

Complexité
Dans le but de mesurer la complexité d'un algorithme de tri, deux quantités sont à observer :

· le nombre d'échanges effectués,

· le nombre de comparaisons effectuées entre éléments du tableau.

tri à bulles en n 2 .

tri rapide en n.log(n).

Voir les démos suivantes :

· VisuTri ;

· la page d'insterstices sur les algorithmes de tri ;

· page de démo de Jason Harrison.