Sort

---

🔷 Combien d'algorithmes de tri ?

Il existe plus d'une dizaine d'algorithmes de tri connus, mais les principaux qu'on enseigne et utilise sont environ 8 à 10.

---

✅ Les 10 algorithmes de tri les plus connus

Algorithme	Complexité Moyenne	Type	Stable	In-Place	Exemple d'utilisation
1. Bubble Sort	O(n²)	Comparatif	✅	✅	Simple, éducatif
2. Selection Sort	O(n²)	Comparatif	❌	✅	Tri d’apprentissage
3. Insertion Sort	O(n²)	Comparatif	✅	✅	Listes presque triées
4. Merge Sort	O(n log n)	Comparatif	✅	❌	Données volumineuses
5. Quick Sort	O(n log n)	Comparatif	❌	✅	Très utilisé en pratique
6. Heap Sort	O(n log n)	Comparatif	❌	✅	Tri de tableaux
7. Counting Sort	O(n + k)	Non-comparatif	✅	❌	Petits entiers
8. Radix Sort	O(nk)	Non-comparatif	✅	✅	Entiers, chaînes
9. Bucket Sort	O(n + k)	Non-comparatif	✅	❌	Nombres flottants
10. Shell Sort	O(n log n)	Comparatif	❌	✅	Version améliorée d’Insertion Sort

---

🧠 Classement rapide par catégories

🔸 Algorithmes simples (O(n²)) :

• Bubble Sort

• Selection Sort

• Insertion Sort

🔸 Algorithmes efficaces (O(n log n)) :

• Merge Sort

• Quick Sort

• Heap Sort

🔸 Algorithmes non comparatifs :

• Counting Sort

• Radix Sort

• Bucket Sort

---

🔧 Exemple simple en C# – Insertion Sort

public static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

---

🔧 Exemple en C# – Quick Sort

public static void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int pivot = arr[(left + right) / 2];
    int index = Partition(arr, left, right, pivot);
    QuickSort(arr, left, index - 1);
    QuickSort(arr, index, right);
}

private static int Partition(int[] arr, int left, int right, int pivot)
{
    while (left <= right)
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right)
        {
            (arr[left], arr[right]) = (arr[right], arr[left]);
            left++; right--;
        }
    }
    return left;
}

---

✅ Conclusion

Il existe au moins 10 algorithmes de tri bien connus, chacun adapté à un contexte spécifique :

• Pour des listes petites ou triées : Insertion Sort

• Pour de grandes données : Merge, Quick ou Heap

• Pour des entiers bornés : Counting ou Radix

---