Algorithmes simples

Algorithmes simples

### 1. Recherche dans une liste (recherche séquentielle)

Pour savoir si une valeur v se trouve dans une liste L, on parcourt la liste élément par élément :

> def recherche(L, v):
> for x in L:
> if x == v:
> return True
> return False

Cette méthode, appelée recherche séquentielle, a un coût proportionnel à la longueur de la liste dans le pire cas (la valeur n'est pas présente, ou se trouve en dernière position) : on dit qu'elle est de complexité linéaire, $O(n)$ où $n=\text{len}(L)$.

Variante : trouver l'indice d'une valeur.

> def indice(L, v):
> for i in range(len(L)):
> if L[i] == v:
> return i
> return -1

On renvoie souvent $-1$ par convention pour signaler que la valeur n'a pas été trouvée.

### 2. Tri par sélection

Le tri par sélection construit la liste triée en répétant le principe suivant : trouver le plus petit élément restant et le placer en tête.

> def tri_selection(L):
> n = len(L)
> for i in range(n):
> indice_min = i
> for j in range(i+1, n):
> if L[j] < L[indice_min]:
> indice_min = j
> L[i], L[indice_min] = L[indice_min], L[i]
> return L

À chaque étape $i$, on cherche le minimum parmi les éléments d'indices $i, i+1, \ldots, n-1$ (la partie non encore triée), puis on l'échange avec l'élément d'indice $i$.

Exemple résolu : trier $[5, 2, 8, 1, 9]$.

- $i=0$ : minimum de $[5,2,8,1,9]$ est $1$ (indice $3$) → échange : $[1,2,8,5,9]$
- $i=1$ : minimum de $[2,8,5,9]$ (indices $1$ à $4$) est $2$, déjà en place : $[1,2,8,5,9]$
- $i=2$ : minimum de $[8,5,9]$ est $5$ (indice $3$) → échange : $[1,2,5,8,9]$
- $i=3$ : minimum de $[8,9]$ est $8$, déjà en place : $[1,2,5,8,9]$ (trié)

### 3. Tri par insertion (alternative)

Le tri par insertion construit la partie triée en insérant chaque nouvel élément à sa bonne place parmi les éléments déjà triés :

> def tri_insertion(L):
> for i in range(1, len(L)):
> cle = L[i]
> j = i - 1
> while j >= 0 and L[j] > cle:
> L[j+1] = L[j]
> j = j - 1
> L[j+1] = cle
> return L

### 4. Calcul de moyenne et de somme

> def somme(L):
> s = 0
> for x in L:
> s = s + x
> return s
>
> def moyenne(L):
> return somme(L) / len(L)

### 5. Calcul itératif du PGCD (algorithme d'Euclide)

Le PGCD (plus grand commun diviseur) de deux entiers $a$ et $b$ se calcule par l'algorithme d'Euclide, fondé sur la propriété $\text{pgcd}(a,b)=\text{pgcd}(b, a \bmod b)$, avec $\text{pgcd}(a,0)=a$ :

> def pgcd(a, b):
> while b != 0:
> a, b = b, a % b
> return a

Exemple résolu : $\text{pgcd}(48, 18)$.

- $(a,b)=(48,18)$ : $48 \bmod 18 = 12$ → nouveau couple $(18, 12)$
- $(18,12)$ : $18 \bmod 12 = 6$ → $(12, 6)$
- $(12,6)$ : $12 \bmod 6 = 0$ → $(6, 0)$
- $b=0$ : on renvoie $a=6$.

Donc $\text{pgcd}(48,18)=6$.

### 6. Résumé des complexités

| Algorithme | Complexité (pire cas) |
|---|---|
| Recherche séquentielle | $O(n)$ |
| Tri par sélection | $O(n^2)$ |
| Tri par insertion | $O(n^2)$ |
| Algorithme d'Euclide | $O(\log(\min(a,b)))$ |