Guide de l'algorithme de tri rapide Python
Explorez l'algorithme de tri rapide en Python. Apprenez la sélection pivot, le partitionnement et la récursivité dans cet exemple de codage interactif.
Aperçu
Quicksort est un algorithme de tri extrêmement rapide et largement utilisé. Comme le tri par fusion, il utilise une approche diviser pour régner. Cependant, le tri rapide trie les éléments « sur place », ce qui rend la mémoire efficace.
L'algorithme fonctionne en sélectionnant un élément « pivot » dans la liste. Il divise ensuite les autres éléments en deux sous-tableaux : ceux inférieurs au pivot et ceux supérieurs au pivot. Ce processus est appliqué de manière récursive aux sous-tableaux.
Bien que le tri rapide ait une complexité dans le pire des cas de O(n²), son temps d'exécution moyen est O(n log n), et il surpasse généralement le tri par fusion dans la pratique en raison de moins d'échecs de cache et d'une surcharge nulle liée à la création de tableaux temporaires.
Sortie de code et d'exécution
Un script de tri rapide récursif concis utilisant des compréhensions de listes pour une lisibilité élevée.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Mise en œuvre étape par étape
- Routines de tri du système où l'empreinte mémoire doit être réduite au minimum
- Tri à usage général dans les frameworks de bibliothèques de langages standard
- Enseignement académique de la mécanique des partitions et du diviser pour régner récursif
Foire aux questions
Comment pouvons-nous éviter la pire complexité de O(n²) dans Quicksort ?
Le pire des cas se produit lorsque le pivot sélectionné est à plusieurs reprises le plus petit ou le plus grand élément. Pour atténuer cela, les développeurs utilisent des stratégies telles que le choix d'un pivot aléatoire ou des valeurs « médiane sur trois ».
Le tri rapide est-il stable ?
Non, le tri rapide standard est instable. Lors du partitionnement, les éléments sont permutés sur de longues plages, ce qui peut modifier l'ordre relatif des éléments en double.
Sujets connexes
Découvrez comment implémenter le tri par fusion en Python. Un exemple interactif, étape par étape, de la stratégie de tri Diviser pour régner.
Algorithmes de tri PythonExplorez les algorithmes de tri Python. Visualisez le tri par bulles et le tri par fusion de manière native dans un contexte IDE de navigateur.
Algorithme de recherche binaire PythonRecherchez des listes triées en temps logarithmique O (log n). Exécutez et comprenez la recherche binaire en Python, y compris la logique étape par étape, les cas extrêmes et les optimisations.