Un algorithme est une série d’étapes logiques et précises qui permettent de résoudre un problème donné. Il s’agit d’une méthode bien définie pour résoudre un problème, qui peut être appliquée de manière reproductible pour résoudre le même problème à chaque fois.
Le premier exemple est le tri à bulles (bubble sort) en Python. Le tri à bulles est un algorithme de tri simple qui compare des éléments adjacents et les échange s’ils sont dans le mauvais ordre. Voici un exemple de code Python pour trier une liste d’entiers avec le tri à bulles :
1
2
3
4
5
6
7
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(0, n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst
Voici une représentation visuelle du tri à bulles pour mieux comprendre comment fonctionne l’algorithme :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Avant le tri : [4, 2, 1, 5, 3]
+---+---+---+---+---+
| 4 | 2 | 1 | 5 | 3 |
+---+---+---+---+---+
^ ^ ^ ^
| | | |
j=0 j=1 j=2 j=3
(i=0)
Après le premier passage : [2, 1, 4, 3, 5]
+---+---+---+---+---+
| 2 | 1 | 4 | 3 | 5 |
+---+---+---+---+---+
^ ^ ^ ^
| | | |
j=0 j=1 j=2 j=3
(i=1)
Après le deuxième passage : [1, 2, 3, 4, 5]
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
^ ^ ^ ^
| | | |
j=0 j=1 j=2 j=3
(i=2)
Le deuxième exemple que je vais vous donner est le tri rapide (quick sort). Le tri rapide est un algorithme de tri récursif qui divise une liste en deux sous-listes, puis trie chaque sous-liste de manière récursive. Voici un exemple de code Python pour trier une liste d’entiers avec le tri rapide :
1
2
3
4
5
6
7
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left_lst = [x for x in lst[1:] if x <= pivot]
right_lst = [x for x in lst[1:] if x > pivot]
return quick_sort(left_lst) + [pivot] + quick_sort(right_lst)