Introduction à l'Algorithmique

Qu'est-ce qu'un Algorithme ?

Un algorithme est une séquence d'instructions précises et non ambiguës qui, lorsqu'elles sont exécutées, accomplissent une tâche spécifique ou résolvent un problème donné.

Exemple : Algorithme de Tri à Bulles

Le tri à bulles compare des valeurs voisines et les échange lorsqu'elles sont dans le mauvais ordre. Un passage fait avancer la plus grande valeur de la partie parcourue vers sa position finale. Les passages suivants portent sur une partie de plus en plus courte du tableau.

procédure triBulles(tableau T)
    n ← longueur(T)
    pour i de n-1 à 1 faire
        pour j de 0 à i-1 faire
            si T[j] > T[j+1] alors
                échanger T[j] et T[j+1]
            fin si
        fin pour
    fin pour
fin procédure

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Exemple d'utilisation
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Avant le tri: {numbers}")
bubble_sort(numbers)
print(f"Après le tri: {numbers}")

Lire le pseudo-code et comprendre les limites

Le pseudo-code décrit les étapes sans dépendre d'un langage. Dans la version Python, les indices servent à comparer les éléments voisins ; l'affectation échange leurs valeurs directement dans la liste. La liste est donc modifiée, puis renvoyée par la fonction. Comparez les deux onglets pour retrouver les mêmes boucles, la même condition et le même échange.

Cette implémentation effectue des comparaisons même si la liste est déjà triée. Le nombre de comparaisons croît quadratiquement avec la taille de la liste : sa complexité est O(n²). Le tri à bulles est utile pour comprendre les boucles et les échanges ; pour trier une liste dans un programme Python courant, utilisez plutôt list.sort()ou sorted().

Pour situer cet exemple parmi d'autres méthodes, poursuivez avec lesstructures de données et algorithmes.