Algorithmes de tri || Python || Structures de données et algorithmes-Tutoriel Python-php.cn

Sorting Algorithms || Python || Data Structures and Algorithms

Algoritmes de tri

1. Tri à bulles

En cela, nous échangeons l'élément supérieur avec son voisin jusqu'à atteindre la fin du tableau. L'élément le plus élevé se trouve désormais en dernière position. Nous modifions donc la limite et la diminuons de 1 par rapport à la précédente. Au pire, nous devons itérer n fois pour trier le tableau.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Copier après la connexion

Algorithme -

Parcourez le tableau et trouvez l'élément maximum, puis échangez-le vers le dernier.
Comparez tous les éléments adjacents et échangez si le plus grand élément est avant le plus petit élément. Continuez ainsi jusqu'à ce que vous atteigniez la fin du tableau.
Maintenir un drapeau : si aucun élément n'est échangé, alors nous pouvons rompre la boucle, car le tableau est trié.

Complexité temporelle :

Meilleur cas - Si le tableau est déjà trié, une seule itération est requise. Complexité temporelle - O(n)
Cas moyen - si le tableau est trié de manière aléatoire, alors complexité temporelle - O(n2)
Pire des cas - si le tableau est par ordre décroissant alors nous aurons besoin de n*2 itérations.

Complexité spatiale - O(1), aucune mémoire supplémentaire requise.

Avantages -

Aucune mémoire supplémentaire requise.
Stable car les éléments gardent leur ordre relatif.

Inconvénients -

Complexité temporelle - O(n2), ce qui est très élevé pour les grands ensembles de données.

Applications-

Peut être utilisé uniquement lorsque l'ensemble de données est très petit et que la simplicité l'emporte sur l'inefficacité en raison de la complexité temporelle élevée.

2. Tri par sélection

En cela, nous trouvons le plus petit élément du tableau et le remplaçons par le premier élément. Ensuite, nous augmentons la limite de 1 et répétons les mêmes étapes jusqu'à atteindre la fin du tableau.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Copier après la connexion

Algorithme -

Parcourez le tableau et trouvez l'élément minimum.
Échangez-le avec le premier élément et augmentez le pointeur de 1.
Répétez ce processus jusqu'à ce que nous atteignions la fin du tableau.

Complexité temporelle : Il a une complexité temporelle de O(n2) dans les trois cas : meilleur, moyen et pire. C'est parce que nous devons sélectionner l'élément minimum et échangez-le à chaque fois, que le tableau soit déjà trié ou non.

Complexité spatiale - O(1), aucune mémoire supplémentaire requise.

Avantages -

Aucune mémoire supplémentaire requise.
Moins d'échanges sont effectués que dans le tri à bulles.

Inconvénients -

Complexité temporelle - O(n2), qui est très élevée pour les grands ensembles de données.
Non stable, car il ne maintient pas l'ordre relatif des éléments égaux.

Applications -

Il peut être utilisé dans des systèmes avec une mémoire limitée car il ne nécessite pas de stockage supplémentaire.
Il est utilisé dans les systèmes où il est essentiel de minimiser le nombre d'échanges, comme dans les systèmes avec des opérations d'écriture lentes.

3. Tri par insertion

C'est un algorithme qui fonctionne en insérant un élément non trié dans sa position correcte en vérifiant itérativement en arrière depuis la position de l'élément jusqu'au début du tableau.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Copier après la connexion

Algorithme -

Partez du deuxième élément du tableau et comparez-le avec le premier élément. Si l'élément actuel est plus petit que le premier élément, échangez-les.
Augmentez maintenant le pointeur et faites ceci pour le troisième élément : comparez-le avec le deuxième et le premier élément.
Répétez le même processus pour le reste des éléments, en les comparant avec tous les éléments précédents, et insérez-les à la position appropriée.

Complexité temporelle :

- Meilleur cas - Si le tableau est déjà trié, une seule itération est requise. La complexité temporelle est O(n)
- Cas moyen - si le tableau est trié aléatoirement, alors la complexité temporelle est O(n2)
- Pire des cas - si le tableau est par ordre décroissant alors nous aurons besoin de n2 itérations.

Complexité spatiale - O(1), aucune mémoire supplémentaire requise.

Avantages -

Aucune mémoire supplémentaire requise.
Stable, car les éléments conservent leur ordre relatif.

Inconvénients -

Complexité temporelle - O(n2), qui est très élevée pour les grands ensembles de données.
Non stable, car il ne maintient pas l'ordre relatif des éléments égaux.

Applications-

Il est efficace pour les scénarios dans lesquels les éléments arrivent en temps réel et doivent être triés, comme les flux de données en direct.

4. Fusionner le tri

Merge Sort est un algorithme qui suit l'approche diviser pour régner. Il comporte deux étapes principales : premièrement, diviser le tableau de manière récursive et deuxièmement, fusionner les tableaux divisés dans un ordre trié.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Copier après la connexion

Algorithme -

Divisez le tableau en deux moitiés en calculant le point médian.
Continuez à diviser jusqu'à ce que la longueur de chaque sous-tableau soit de 1.
Appelez la fonction de fusion sur les deux moitiés : la moitié gauche et la moitié droite.
Utilisez trois pointeurs pour le processus de fusion :

Le premier pointeur pour le demi-tableau gauche.
Le deuxième pointeur pour le demi-tableau droit.
Le troisième pointeur pour le tableau trié.

Parcourez les deux moitiés et comparez leurs éléments. Insérez le plus petit élément dans le tableau trié et incrémentez le pointeur correspondant de 1.
Répétez ce processus de manière récursive jusqu'à ce que l'ensemble du tableau soit trié.

Complexité temporelle : Le tri par fusion a une complexité temporelle de O(n log n) dans les trois cas : meilleur, moyen et pire. En effet, que le tableau soit déjà trié ou non, les mêmes étapes sont suivies pour chaque division et fusion.

O(log n) - La taille du tableau est réduite de moitié à chaque étape pendant la phase de division.

O(n) - Pendant le processus de fusion, nous devons parcourir tous les éléments une fois.

Donc, la complexité temporelle totale est O (n) * O (log n) = O (n log n)

Complexité spatiale - O(n), Une mémoire supplémentaire est requise pendant le processus de fusion pour stocker les tableaux temporaires.

Avantages -

Stable, car les éléments conservent leur ordre relatif.
La complexité temporelle est O (n log n), même pour les grands ensembles de données.
Convient au traitement parallèle car les sous-tableaux sont fusionnés indépendamment.

Inconvénients -

Complexité temporelle - O(n2), ce qui est très élevé pour les grands ensembles de données.
Une mémoire supplémentaire est requise pour le processus de fusion.
Pas en place car une mémoire supplémentaire est requise.
Plus lent que QuickSort en général pour la plupart des ensembles de données.

Applications -

Il est utilisé dans des situations où les données sont trop volumineuses pour tenir en mémoire, comme la fusion de fichiers volumineux.
Il est utilisé pour trier les listes chaînées car l'accès aléatoire n'est pas requis.

5. Tri rapide

Quick Sort est un algorithme qui suit l'approche diviser pour régner. Nous choisissons un élément pivot et partitionnons le tableau autour de l'élément pivot après avoir placé le pivot dans sa position triée correcte.

La première étape consiste à choisir l'élément pivot puis à partitionner le tableau autour du pivot. Tous les éléments plus petits que le pivot seront à gauche et tous les éléments supérieurs au pivot seront à sa droite. Le pivot est alors dans sa bonne position triée. De manière récursive, le même processus est appliqué en divisant le tableau en deux moitiés : la première moitié contient les éléments avant le pivot, et la seconde moitié contient les éléments après le pivot. Ce processus est répété jusqu'à ce que la longueur de chaque sous-tableau atteigne 1.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Copier après la connexion

Algorithme -

Divisez le tableau en deux moitiés en calculant le point médian.
Choisissez un pivot ; n'importe quel élément peut être choisi comme pivot.
Parcourez le tableau et comparez chaque élément avec le pivot.
Placez tous les éléments plus petits que le pivot à gauche et tous les éléments supérieurs au pivot à droite.
Échangez le pivot avec le pointeur gauche pour que le pivot soit dans sa position triée correcte.
Répétez ce processus de manière récursive jusqu'à ce que la longueur de la partition soit supérieure à 1.

Complexité temporelle :

1. Meilleur cas - Complexité temporelle - O(n log n), lorsque le pivot divise le tableau en deux moitiés égales.
2. Cas moyen - Complexité temporelle - O(n log n), lorsque le pivot divise le tableau en deux moitiés égales. Mais pas forcément égal.
3. Dans le pire des cas - Complexité temporelle - O(n2) , Quand -

Le plus petit élément est choisi comme pivot dans un tableau déjà trié.
Le plus grand élément est choisi comme pivot dans un tableau trié par ordre décroissant.

O(log n) - La taille du tableau est réduite de moitié à chaque étape pendant la phase de division.

O(n) - Lors de la commande des éléments.

Donc, la complexité temporelle totale est O (n) * O (log n) = O (n log n)

Complexité spatiale :

Meilleur cas et cas moyen - O(log n) - pour la pile récursive.
Pire des cas - O(n) - pour la pile récursive.

Avantages -

Efficace pour les grands ensembles de données, sauf si le pivot est mal choisi.
Il est compatible avec le cache car nous travaillons sur le même tableau pour trier et ne copier les données vers aucun tableau auxiliaire.
L'un des algorithmes à usage général les plus rapides pour les données volumineuses lorsque la stabilité n'est pas requise.

Inconvénients -

Complexité temporelle - O(n2), ce qui est très élevé pour les grands ensembles de données.
Non stable, car il ne maintient pas l'ordre relatif des éléments égaux.

Applications -

Il est utilisé dans les bibliothèques et les frameworks de programmation. Par exemple : la fonction sorted() de Python et Array.sort() de Java sont basées sur un tri rapide.
Il est utilisé dans l'optimisation des requêtes de base de données en triant efficacement les lignes lors de l'exécution de la requête.
Il fonctionne bien pour le tri en mémoire d'ensembles de données volumineux en raison de ses propriétés respectueuses du cache.

6. Tri par tas

Heap Sort est un algorithme de tri basé sur la comparaison. Il s'agit d'une extension de Selection Sort. Dans Heap Sort, nous créons un tas binaire et échangeons l'élément maximum ou minimum avec le dernier élément. Ensuite, nous réduisons la taille du tas de 1. Ce processus est répété jusqu'à ce que la longueur du tas soit supérieure à 1.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Copier après la connexion

Algorithme -

Créez un tas maximum en utilisant le processus heapify. Heapify est une méthode utilisée pour conserver la propriété tas d'une structure de données de tas binaire.
Si le tableau est de taille n, il contient n//2 nœuds parents.
Pour un parent à l'index i :

a.Son enfant gauche est à l'index 2i 1

b. Son enfant droit est à l'index 2i 2

Parcourez tous les sous-arbres avec des parents de l'index n//2 à 0 et appelez la fonction heapify sur eux.
Maintenant, le tableau devient un tas maximum, avec le plus grand élément à l'index 0.
Échangez le premier élément avec le dernier élément du tas et diminuez la taille du tas de 1.
Répétez ce processus jusqu'à ce que la longueur du tas soit supérieure à 1

Complexité temporelle : Heap Sort a une complexité temporelle de O(n log n) dans les trois cas : meilleur, moyen et pire. En effet, que le tableau soit déjà trié ou non, les mêmes étapes sont suivies chaque fois qu'un tas maximum est créé et qu'un élément est échangé.

O(log n) - Pour créer un tas maximum

O(n) - Lorsque le tas maximum est créé et qu'un élément est échangé n fois.

Donc, la complexité temporelle totale est O (n) * O (log n) = O (n log n)

Complexité spatiale : Pour tous les cas - O( log n) - pour la pile récursive.

Avantages -

La complexité temporelle est O (n log n), même pour les grands ensembles de données.
L'utilisation de la mémoire est presque constante.

Inconvénients -

Non stable, car il ne maintient pas l'ordre relatif des éléments égaux.
De nombreux échanges sont nécessaires par rapport au tri par fusion.

Applications -

Il est utile pour implémenter des files d'attente prioritaires où l'extraction de l'élément maximum ou minimum est fréquente.
Utile dans les systèmes où le tri sur place est nécessaire et où l'utilisation de la mémoire est critique.
Il est utilisé dans des scénarios où des classements sont nécessaires.

7. Tri par comptage et tri par base

Counting Sort est un algorithme de tri sans comparaison. Il est particulièrement efficace lorsque la plage de valeurs d’entrée est petite par rapport au nombre d’éléments à trier. L'idée de base derrière Counting Sort est de compter la fréquence de chaque élément distinct dans le tableau d'entrée et d'utiliser ces informations pour placer les éléments dans leurs positions triées correctes.

Radix Sort utilise Counting Sort comme sous-programme. Il applique le tri par comptage à chaque chiffre d'un nombre et trie à plusieurs reprises jusqu'à ce qu'il traite tous les chiffres du plus grand nombre du tableau.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Copier après la connexion

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Copier après la connexion

Algorithme -

Trouvez le nombre maximum dans le tableau et déterminez le nombre de chiffres (d) qu'il contient. Si la longueur du nombre est d, Counting Sort est appelé d fois sur le tableau.
Tri du comptage d'appels pour chaque chiffre du tableau, en commençant par celui des unités, puis celui des dizaines, et ainsi de suite.
Dans le tri Comptage :

Tout d'abord, créez un tableau d'index et mappez les éléments en fonction de leurs valeurs. Par exemple, si un chiffre est 4, incrémentez la valeur au 4ème index du tableau d'index.
Créez un tableau de somme de préfixes à partir du tableau d'index.
À l'aide du tableau de somme de préfixes, créez un nouveau tableau trié égal à la longueur du tableau d'entrée
Par exemple, si le tableau de somme de préfixes a une valeur de 2 à l'index 1, placez la valeur 1 à la position 2 dans le tableau trié et décrémentez la valeur dans le tableau de somme de préfixes de 1

Complexité temporelle :

Tri par comptage a une complexité temporelle de O(n k), où n est le nombre d'éléments à trier et k est la plage de valeurs (taille du tableau d'index). Cette complexité est valable pour les trois cas : le meilleur, la moyenne et le pire.

En effet, que le tableau soit déjà trié ou non, les mêmes étapes sont suivies à chaque fois.

La complexité temporelle du

Radix Sort augmente d'un facteur d, où d est le nombre de chiffres du plus grand nombre du tableau. La complexité temporelle est O (d * (nk))

Donc, la complexité temporelle totale est O (d) * O(n k) = O (d * (n k))

Complexité spatiale : pour tous les cas - O(n k), où n est la longueur du tableau d'entrée et k est la plage de valeurs dans le tableau d'index.

Avantages -

Stable car les éléments conservent leur ordre relatif.
Le tri par comptage est généralement plus rapide que tous les algorithmes de tri basés sur des comparaisons, tels que le tri par fusion et le tri rapide, si la plage d'entrée est de l'ordre du nombre d'entrées.

Inconvénients -

Le tri par comptage ne fonctionne pas sur les valeurs décimales.
Le tri par comptage est inefficace si la plage de valeurs à trier est très large.
Algorithme de tri non en place, car il utilise un espace supplémentaire O(O(n m)).

Applications -

Il est utilisé dans des applications telles que le comptage des occurrences de caractères dans les chaînes.
Utile pour trier des entiers avec une large plage de valeurs, tels que des identifiants ou des numéros de téléphone.
Efficace pour trier des données avec plusieurs clés, comme des dates ou des tuples.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!