Tri rapide avec Python

Le tri rapide est un algorithme de tri couramment utilisé avec une complexité temporelle de O(nlogn). Dans les applications pratiques, le tri rapide est généralement beaucoup plus rapide que les autres algorithmes de tri. Python fournit de nombreuses fonctions de tri intégrées, mais il est toujours important de comprendre et d'implémenter le tri rapide. Dans cet article, nous allons implémenter l'algorithme de tri rapide via Python.

Le tri rapide fonctionne en sélectionnant une valeur pivot (pivot), puis en plaçant tous les éléments de la liste qui sont plus petits que la valeur pivot dans une sous-liste et en plaçant tous les éléments supérieurs à la valeur pivot dans une autre sous-liste. Les deux sous-listes sont ensuite rapidement triées de manière récursive. Finalement, toutes les sous-listes seront triées de manière récursive puis fusionnées en une seule liste triée.

Voici le code pour implémenter le tri rapide en Python :

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

Dans le code ci-dessus, on vérifie d'abord la longueur de la liste. Si la longueur de la liste est inférieure à 2, nous renvoyons la liste d'origine. Sinon, nous sélectionnons le premier élément de la liste comme valeur pivot. Nous utilisons ensuite des compréhensions de liste pour placer les éléments inférieurs ou égaux à la valeur pivot dans une liste, et les éléments supérieurs à la valeur pivot dans une autre liste. Ensuite, nous trions récursivement les listes plus petites et plus grandes et concaténons les listes triées ensemble, la valeur pivot étant placée au milieu des listes concaténées.

Cet algorithme doit choisir un numéro de référence approprié. Si le numéro de base choisi s'avère être la valeur la plus grande (ou la plus petite) de la liste, alors la taille de la sous-liste triée de manière récursive est réduite de 1 seulement. Dans ce cas, la complexité temporelle de l’algorithme de tri rapide peut dégénérer en O(n2). Pour éviter cela, nous pouvons utiliser la méthode de sélection aléatoire de la valeur de base. Cette méthode garantit la taille moyenne des sous-listes triées de manière récursive dans les cas où la valeur de base n'est pas la plus grande (ou la plus petite) valeur de la liste.

Voici le code Python pour utiliser la sélection aléatoire de la valeur de référence :

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

Dans le code ci-dessus, nous sélectionnons d'abord au hasard une valeur de référence à l'aide de la fonction random.randint(). Ensuite, nous plaçons les éléments inférieurs ou égaux à la valeur de base dans une liste et les éléments supérieurs à la valeur de base dans une autre liste, similaire à l'implémentation précédente.

Pour résumer, nous avons implémenté l'algorithme de tri rapide via Python et utilisé la méthode de sélection aléatoire de la valeur de référence pour éviter le déséquilibre de la taille de la sous-liste triée de manière récursive. Cet algorithme est basé sur l'idée de ​​​​Divide and Conquer, qui permet de trier rapidement la liste avec une complexité temporelle de O(nlogn) en moyenne.

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!