Algorithmes de base

#AlgorithmesCopier le lien

Définition, propriétés et exemples d'algorithmes classiques.

#Qu'est-ce qu'un algorithme ?Copier le lien

Un algorithme est une séquence finie d'instructions précises et compréhensibles permettant de résoudre un problème ou d'accomplir une tâche.

#PropriétésCopier le lien

• Finitude : L'algorithme doit se terminer en un nombre fini d'étapes
• Précision : Chaque instruction doit être claire et non ambiguë
• Entrées : Zéro ou plusieurs valeurs en entrée
• Sorties : Une ou plusieurs valeurs en sortie
• Efficacité : Chaque instruction doit être réalisable en temps fini

#Algorithmes de rechercheCopier le lien

#Recherche linéaireCopier le lien

La recherche linéaire est l'algorithme de recherche le plus simple. Il consiste à parcourir un tableau élément par élément jusqu'à trouver la valeur recherchée.

Principe :

1. Commencer au premier élément
2. Comparer l'élément courant avec la valeur recherchée
3. Si trouvé, retourner l'index
4. Sinon, passer à l'élément suivant
5. Répéter jusqu'à la fin du tableau

Complexité : O(n)

#Recherche dichotomiqueCopier le lien

La recherche dichotomique est un algorithme plus efficace qui nécessite un tableau trié. Elle divise récursivement l'espace de recherche en deux.

Principe :

1. Déterminer les bornes gauche et droite
2. Calculer le milieu
3. Comparer l'élément du milieu avec la valeur recherchée
4. Si trouvé, retourner l'index
5. Si la valeur recherchée est inférieure, chercher dans la moitié gauche
6. Si la valeur recherchée est supérieure, chercher dans la moitié droite
7. Répéter jusqu'à trouver l'élément ou épuiser l'espace de recherche

Complexité : O(log n)

#Algorithmes de triCopier le lien

#Tri à bullesCopier le lien

Le tri à bulles est un algorithme simple de tri par comparaison.

Principe :

1. Parcourir le tableau de gauche à droite
2. Comparer chaque paire d'éléments adjacents
3. Échanger les éléments si nécessaire
4. Répéter jusqu'à ce qu'aucun échange ne soit nécessaire

Complexité : O(n²)

#Tri rapide (QuickSort)Copier le lien

Le tri rapide est un algorithme de tri efficace basé sur le principe de "diviser pour régner".

Principe :

1. Choisir un élément pivot
2. Réorganiser le tableau pour que les éléments inférieurs au pivot soient à gauche et les supérieurs à droite
3. Appliquer récursivement le tri aux sous-tableaux

Complexité :

• Meilleur cas : O(n log n)
• Pire cas : O(n²)