Algorithmes de tri

Un algorithme de tri est un algorithme qui organise une séquence de données selon une méthode de tri spécifique ; les données triées peuvent ensuite être placées dans un tableau ordonné.

TriIl désigne le processus de réorganisation d'un ensemble de données (comme un tableau ou une liste) dans un ordre spécifique (croissant ou décroissant).

La base du tri est généralement une certaine propriété des éléments de donnéesClécomme la grandeur des nombres, l'ordre lexicographique des chaînes, etc.

Le tri est l'un des problèmes algorithmiques les plus fondamentaux et centraux en informatique. Qu'il s'agisse d'organiser des contacts, d'analyser des notes d'examen ou d'optimiser des requêtes de base de données, les algorithmes de tri sont partout.

Comprendre différents algorithmes de tri nous aide non seulement à résoudre des problèmes pratiques, mais c'est aussi un excellent moyen de comprendre en profondeur les idées de conception et d'analyse d'algorithmes.

Classification des algorithmes de tri

Les algorithmes de tri peuvent être classés selon plusieurs dimensions, et la classification la plus courante repose sur leurcomplexité temporelleet leurcomplexité spatiale。

Dimension de classification Catégorie Description Algorithmes typiques
Complexité temporelle Niveau O(n²) simple et intuitif, mais peu efficace, adapté aux données de petite taille. Tri à bulles, tri par sélection, tri par insertion
Niveau O(n log n) efficacité relativement élevée, et constitue le premier choix pour le traitement de données à grande échelle. Tri rapide, tri fusion, tri par tas
Complexité spatiale Tri en place N'utilise qu'une quantité constante d'espace supplémentaire pendant le processus de tri. Tri à bulles, tri par sélection, tri par insertion, tri de Shell, tri par tas, tri rapide.
Tri non en place Un espace supplémentaire proportionnel à la taille des données est nécessaire pendant le processus de tri. Tri fusion, tri comptage, tri par compartiments, tri par base.
Stabilité Tri stable L'ordre relatif des éléments égaux reste inchangé après le tri. Tri à bulles, tri par insertion, tri fusion, tri comptage, tri par compartiments, tri par base.
Tri instable L'ordre relatif des éléments égaux peut changer après le tri. Tri par sélection, tri de Shell, tri par tas, tri rapide

Explication des concepts clés :

  • Complexité temporelleMesure l'évolution du temps d'exécution d'un algorithme à mesure que la taille des données augmente.
  • Complexité spatialeMesure la quantité d'espace de stockage supplémentaire nécessaire pendant l'exécution d'un algorithme.
  • StabilitéPour les éléments de valeurs égales, si leur ordre relatif reste inchangé après le tri. C'est très important dans le tri multi-clés.

L'organigramme suivant montre comment faire un choix préliminaire parmi plusieurs algorithmes classiques selon différents scénarios de besoins :


Algorithmes de tri de base de niveau O(n²)

Ces algorithmes sont simples dans leur concept et constituent le point de départ pour comprendre la logique de tri.

Tri à bulles

Idée principaleParcourir de façon répétée la séquence à trier, en comparant deux éléments adjacents à la fois, et en les échangeant s'ils sont dans le mauvais ordre. Chaque parcours fait remonter le plus grand (ou le plus petit) élément de la partie non triée actuelle à sa position correcte.

Étapes de l'algorithme:

  1. Comparer les éléments adjacents. Si le premier est supérieur au second (pour un ordre croissant), les échanger.
  2. Faire de même pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. Après cette étape, le dernier élément sera le plus grand nombre.
  3. Répéter les étapes ci-dessus pour tous les éléments sauf le dernier (car chaque tour détermine un élément final).
  4. Continuer à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois, jusqu'à ce qu'il n'y ait plus de paire de nombres à comparer.

Implémentation du code:

Exemple

def bubble_sort(arr):
    """
Tri à bulles (ordre croissant)
:param arr: La liste à trier
    """

    n = len(arr)
    # La boucle externe contrôle le nombre de passes nécessaires (n-1 passes)
    for i in range(n - 1):
        # La boucle interne effectue la comparaison et l'échange des éléments adjacents
        # Après chaque passe, les derniers i+1 éléments sont déjà triés, donc la plage de comparaison va de 0 à n-1-i
        for j in range(0, n - 1 - i):
            if arr[j] > arr[j + 1]:  # Si l'élément précédent est plus grand que l'élément suivant
                # Échanger les positions des deux éléments
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Données de test
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Tableau d'origine :", test_data)
sorted_data = bubble_sort(test_data.copy()) # Utiliser une copie pour éviter de modifier les données d'origine
print("Après le tri à bulles :", sorted_data)

Sortie :

原始数组: [64, 34, 25, 12, 22, 11, 90]
冒泡排序后: [11, 12, 22, 25, 34, 64, 90]

Analyse des performances:

  • Complexité temporelleMeilleur cas O(n) (réalisable avec optimisation lorsque déjà trié), pire cas et cas moyen O(n²).
  • Complexité spatiale: O(1), c'est un tri en place.
  • Stabilité: stable.

Tri par sélection

Idée principaleTrouver le plus petit (ou le plus grand) élément dans la séquence non triée, le placer au début de la séquence triée, puis continuer à trouver le plus petit (le plus grand) élément parmi les éléments non triés restants et le placer à la fin de la séquence triée. Continuer ainsi jusqu'à ce que tous les éléments soient triés.

Étapes de l'algorithme:

  1. État initial : la séquence entière est la région non triée.
  2. Lors de la i-ème passe (i commençant à 0) du tri, la région non triée actuelle estarr[i...n-1]Dans cette région, sélectionnez l'enregistrement ayant la plus petite cléarr[min_index]。
  3. vaarr[min_index]Avec le premier enregistrement de la région non triéearr[i]Échangez. De cette façon,arr[0...i]Ensuite, la région triée est formée.
  4. Après n-1 passes, le tableau est trié.

Implémentation du code:

Exemple

def selection_sort(arr):
    """
Tri par sélection (croissant)
:param arr: La liste à trier
    """

    n = len(arr)
    for i in range(n):
        # Supposons que l'élément à l'indice actuel i soit le plus petit
        min_index = i
        # Trouver un élément plus petit dans l'intervalle de i+1 à n-1
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j # Mettre à jour l'indice du plus petit élément
        # Échanger le plus petit élément trouvé avec l'élément à la position i
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Test
test_data = [64, 25, 12, 22, 11]
print("Tableau d'origine :", test_data)
print("Après le tri par sélection :", selection_sort(test_data.copy()))

Sortie :

原始数组: [64, 25, 12, 22, 11]
选择排序后: [11, 12, 22, 25, 64]

Analyse des performances:

  • Complexité temporelleToujours O(n²), car des comparaisons complètes sont nécessaires, que les données soient triées ou non.
  • Complexité spatiale: O(1), tri en place.
  • Stabilité:instable. Par exemple, la séquence[5, 8, 5, 2, 9], au premier tour, le premier [élément] sera5et2échangé, ce qui brise les deux5L'ordre d'origine.

Tri par insertion

Idée cléEn construisant une séquence ordonnée, pour les données non triées, parcourir la séquence triée en sens inverse, trouver la position appropriée et l'insérer. C'est comme ranger des cartes à jouer.

Étapes de l'algorithme:

  1. Considérer le premier élément comme la séquence triée.
  2. Prenez l'élément suivant et parcourez à rebours la séquence d'éléments triés.
  3. Si l'élément trié est supérieur au nouvel élément, déplacez l'élément trié à la position suivante.
  4. Répétez l'étape 3 jusqu'à ce que vous trouviez une position où l'élément trié est inférieur ou égal au nouvel élément.
  5. Après avoir inséré le nouvel élément à cette position.
  6. Répétez les étapes 2-5 jusqu'à ce que tous les éléments soient traités.

Implémentation du code:

Exemple

def insertion_sort(arr):
    """
Tri par insertion (ordre croissant)
:param arr: La liste à trier
    """

    n = len(arr)
    # Commencez à partir du deuxième élément (index 1) car le premier élément est déjà trié par défaut
    for i in range(1, n):
        key = arr[i]  # L'élément actuel à insérer
        j = i - 1     # Indice du dernier élément de la séquence triée
        # Parcourez la séquence triée de la fin vers le début pour trouver la position d'insertion de key
        # En même temps, déplacez d'une position vers l'arrière les éléments supérieurs à key
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # Insérer key à la position correcte trouvée
        arr[j + 1] = key
    return arr

# Test
test_data = [12, 11, 13, 5, 6]
print("Tableau d'origine :", test_data)
print("Après le tri par insertion :", insertion_sort(test_data.copy()))

Sortie :

原始数组: [12, 11, 13, 5, 6]
插入排序后: [5, 6, 11, 12, 13]

Analyse des performances:

  • Complexité temporelleMeilleur cas O(n) (déjà trié), cas défavorable et moyen O(n²).
  • Complexité spatiale: O(1), tri en place.
  • Stabilité: stable.
  • Caractéristiques: Pour des données de petite échelle ou presque triées, le tri par insertion est très efficace. C'est l'algorithme vers lequel les algorithmes de tri avancés (comme Timsort) basculent pour les données de petite échelle.

Algorithmes de tri efficaces de niveau O(n log n)

Lorsque la taille des données augmente, les algorithmes en O(n²) deviennent très lents. Les algorithmes plus efficaces suivants sont les piliers de la pratique de l'ingénierie.

Tri rapide

Idée principale:Diviser pour régnerSélectionner un élément pivot. En une passe de tri, partitionner les enregistrements à trier en deux parties indépendantes, où les clés d'une partie sont toutes inférieures aux clés de l'autre partie ; puis trier ces deux parties séparément pour rendre toute la séquence ordonnée.

Étapes de l'algorithme:

  1. Sélectionner le pivotChoisir un élément de la séquence et l'appeler le "pivot".
  2. Opération de partitionnementRéorganiser la séquence de sorte que tous les éléments plus petits que le pivot soient placés avant lui et que tous les éléments plus grands que le pivot soient placés après lui (les nombres égaux peuvent aller d'un côté ou de l'autre). Une fois cette partition terminée, le pivot est dans sa position finale au milieu de la séquence. C'est ce qu'on appelle l'opération de partitionnement.
  3. trier récursivementTrier récursivement la sous-séquence contenant les éléments plus petits que le pivot et la sous-séquence contenant les éléments plus grands que le pivot.

Implémentation du code:

Exemple

def quick_sort(arr):
    """
Tri rapide (croissant) - Fonction principale
    """

    def _quick_sort(arr, low, high):
        if low < high:
            # pi est l'indice de partition, arr[pi] est maintenant à la bonne position
            pi = partition(arr, low, high)
            # Trier récursivement les sous-tableaux avant et après la partition
            _quick_sort(arr, low, pi - 1)
            _quick_sort(arr, pi + 1, high)

    def partition(arr, low, high):
        """
Fonction de partition, sélectionner le dernier élément comme pivot
:return: l'indice de la position finale correcte de l'élément pivot
        """

        pivot = arr[high]  # Choisir un pivot
        i = low - 1        # Pointe vers la fin du sous-tableau des éléments inférieurs au pivot
        for j in range(low, high):
            # Si l'élément actuel est inférieur ou égal au pivot
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i] # Échanger
        # Placer l'élément pivot à la position correcte (i+1)
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    _quick_sort(arr, 0, len(arr) - 1)
    return arr

# Test
test_data = [10, 80, 30, 90, 40, 50, 70]
print("Tableau d'origine :", test_data)
print("Après le tri rapide :", quick_sort(test_data.copy()))

Sortie :

原始数组: [10, 80, 30, 90, 40, 50, 70]
快速排序后: [10, 30, 40, 50, 70, 80, 90]

Analyse des performances:

  • Complexité temporelleCas moyen O(n log n), pire cas O(n²) (lorsque le tableau est déjà trié ou trié dans l'ordre inverse et que le pivot est mal choisi). Le pire cas peut être largement évité en sélectionnant aléatoirement le pivot ou en utilisant la méthode « médiane de trois ».
  • Complexité spatiale: En moyenne O(log n) (pile d'appels récursifs), dans le pire des cas O(n).
  • Stabilité:instable。

Tri par fusion

Idée principale:Diviser pour régnerUne application typique. Fusionner des sous-séquences déjà triées pour obtenir une séquence complètement triée. C'est-à-dire, d'abord trier chaque sous-séquence, puis ordonner les segments de sous-séquences les uns par rapport aux autres.

Étapes de l'algorithme:

  1. DiviserDiviser l'intervalle actuel en deux parties, c'est-à-dire trouver le point de séparationmid = (low + high)/2。
  2. RégnerTrier récursivement les deux sous-intervallesarr[low...mid]etarr[mid+1...high]Effectuer le tri fusion. La condition d'arrêt de la récursion est que la longueur du sous-intervalle soit 1 (un élément est considéré comme naturellement ordonné).
  3. FusionnerFusionner deux sous-intervalles triés en un intervalle trié.

Implémentation du code:

Exemple

def merge_sort(arr):
    """
Tri fusion (croissant) - Fonction principale
    """

    if len(arr) > 1:
        mid = len(arr) // 2  # Trouver le point milieu et diviser le tableau
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Trier récursivement les moitiés gauche et droite
        merge_sort(left_half)
        merge_sort(right_half)

        # Fusionner les deux sous-tableaux triés
        i = j = k = 0
        # Comparer les éléments des sous-tableaux gauche et droit, placer le plus petit dans le tableau d'origine
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Vérifier s'il reste des éléments (moitié gauche ou moitié droite)
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Test
test_data = [38, 27, 43, 3, 9, 82, 10]
print("Tableau d'origine :", test_data)
print("Après le tri fusion :", merge_sort(test_data.copy()))

Sortie :

原始数组: [38, 27, 43, 3, 9, 82, 10]
归并排序后: [3, 9, 10, 27, 38, 43, 82]

Analyse des performances:

  • Complexité temporelleLes cas meilleur, pire et moyen sont tous O(n log n). Les performances sont très stables.
  • Complexité spatialeO(n), nécessitant un espace supplémentaire égal au tableau d'origine pour la fusion.
  • Stabilité: stable.

Tri par tas

Idée principale: utiliserTasUn algorithme de tri conçu pour cette structure de données. Un tas est une structure d'arbre binaire presque complète qui satisfait également la propriété du tas : la valeur d'un nœud parent est toujours supérieure ou égale (tas max) ou inférieure ou égale (tas min) à la valeur de n'importe quel nœud enfant.

Étapes de l'algorithme:

  1. Construire un tas maxConstruire la séquence à trier en un tas max. À ce stade, la valeur maximale de toute la séquence est le nœud racine au sommet du tas.
  2. Échanger le sommet du tas avec le dernier élémentÉchangez l'élément au sommet (le maximum) avec le dernier élément ; le dernier élément est maintenant le maximum.
  3. Ajuster la structure du tas: pour les éléments restantsn-1Reconstruire les éléments restants en un tas max, ce qui donne la valeur la plus grande suivante. Échangez-la avec le nouveau dernier élément (position n-1).
  4. Répéter l'exécutionRépétez les étapes 2 et 3 jusqu'à ce que la taille du tas soit 1 ; le tri est terminé.

Implémentation du code:

Exemple

def heap_sort(arr):
    """
Tri par tas (croissant) - Utilisation d'un tas max
    """

    n = len(arr)

    # Étape 1 : construire le tas max. Commencez l'ajustement vers le haut à partir du dernier nœud non-feuille
    # Indice du dernier nœud non-feuille = n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Étapes 2 & 3 : Extraire l'élément supérieur (maximum) un par un et ajuster le tas
    for i in range(n - 1, 0, -1):
        # Échanger l'élément supérieur actuel (maximum) avec le dernier élément
        arr[i], arr[0] = arr[0], arr[i]
        # Ajuster les éléments restants pour en faire à nouveau un tas max, avec la taille du tas définie à i
        heapify(arr, i, 0)
    return arr

def heapify(arr, n, i):
    """
Ajuster le sous-arbre enraciné en i pour en faire un tas max
:param arr: tableau du tas
:param n: taille actuelle du tas
:param i: indice de la racine actuelle
    """

    largest = i         # Initialiser la valeur maximale comme racine
    left = 2 * i + 1    # Indice de l'enfant gauche
    right = 2 * i + 2   # Indice de l'enfant droit

    # Si l'enfant gauche existe et est supérieur à la racine
    if left < n and arr[left] > arr[largest]:
        largest = left
    # Si l'enfant droit existe et est supérieur au maximum actuel
    if right < n and arr[right] > arr[largest]:
        largest = right
    # Si le maximum n'est pas la racine, échangez et ajustez récursivement le sous-tas brisé
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Test
test_data = [4, 10, 3, 5, 1]
print("Tableau d'origine :", test_data)
print("Après le tri par tas :", heap_sort(test_data.copy()))

Sortie :

原始数组: [4, 10, 3, 5, 1]
堆排序后: [1, 3, 4, 5, 10]

Analyse des performances:

  • Complexité temporelleLes cas meilleur, pire et moyen sont tous O(n log n).
  • Complexité spatiale: O(1), tri en place.
  • Stabilité:instable。

Résumé de la comparaison des performances des algorithmes

Pour comparer plus intuitivement les caractéristiques des algorithmes ci-dessus, nous les résumons dans le tableau suivant :

算法 Complexité temporelle moyenne Complexité temporelle dans le pire des cas Complexité spatiale Stabilité Fonctionnalités principales
Tri à bulles O(n²) O(n²) O(1) Stable Simple, faible efficacité, adapté à l'enseignement.
Tri par sélection O(n²) O(n²) O(1) instable Moins d'échanges, mais un nombre fixe et élevé de comparaisons.
Tri par insertion O(n²) O(n²) O(1) Stable Efficace pour des données à petite échelle ou presque triées.
Tri rapide O(n log n) O(n²) O(log n) instable Meilleure performance moyenne, est l'algorithme de tri le plus largement utilisé.
Tri par fusion O(n log n) O(n log n) O(n) Stable Performances stables, mais nécessite de l'espace supplémentaire. Souvent utilisé pour le tri externe.
Tri par tas O(n log n) O(n log n) O(1) instable Tri en place et O(n log n) même dans le pire des cas.

Exercices pratiques

Après l'apprentissage théorique, la pratique concrète est le meilleur moyen de consolider les connaissances.

Exercice 1 : Choix et implémentation d'algorithmes

Étant donné les scénarios suivants, quel algorithme de tri choisiriez-vous ? Expliquez brièvement vos raisons.

  1. Trier un tableau contenant 10 nombres.
  2. Trier une liste chaînée de 1 million d'objets étudiants par identifiant étudiant, en exigeant la stabilité.
  3. Trier un grand tableau dans un système embarqué à mémoire limitée.
  4. Besoin d'obtenir les K plus grands éléments d'un flux de données en temps réel.

Approche de la réponse de référence:

  1. Tri par insertionPetite taille de données ; le tri par insertion est simple, adapté aux données presque triées, et a un faible facteur constant.
  2. Tri fusionGrande taille de données, un tri stable est requis, et la structure de liste chaînée permet de réaliser l'opération de fusion du tri fusion en espace O(1) (simplement en modifiant les pointeurs).
  3. Tri par tasMémoire limitée, un tri en place est nécessaire, et le tri par tas garantit une performance O(n log n) même dans le pire cas.
  4. Maintenir un tas min de taille KParcourez le flux de données et utilisez un tas pour maintenir les K plus grands éléments actuels. Ce n'est pas un tri complet, mais cela exploite les propriétés d'un tas.

Exercice 2 : Débogage et optimisation du code

Le tri à bulles ci-dessous a un petit bug et un endroit qui peut être optimisé ; veuillez les trouver et les corriger.

Exemple

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

Indice:

  • Condition de comparaisonarr[j] > arr[j]Toujours faux.
  • La borne de la boucle interne peut être optimisée, car après chaque tour, les éléments de fin sont déjà triés.

Exercice 3 : implémentation pratique

Essayez de l'implémenter vous-même à partir de zéroQuicksort, et réfléchissez :

  • Si le benchmarkpivotQue se passe-t-il si le premier élément est toujours choisi comme pivot, lors du tri d'un tableau déjà trié ?
  • Comment modifierpartitionModifiez la fonction de partition pour qu'elle devienne un « tri rapide à trois voies », qui peut gérer plus efficacement les tableaux comportant de nombreux éléments dupliqués.
autres extensions