Tri rapide Python
Exemples Python3Le tri rapide utilise la stratégie diviser pour régner pour diviser une séquence (liste) en deux sous-séquences plus petites et plus grandes, puis trie récursivement les deux sous-séquences.
Les étapes sont :
- Choisir une valeur de pivot : choisir un élément dans la séquence, appelé « pivot » ;
- Partitionnement : réorganiser la séquence, tous les éléments plus petits que le pivot sont placés avant le pivot, tous les éléments plus grands que le pivot sont placés après le pivot (les nombres égaux au pivot peuvent aller d'un côté ou de l'autre). Une fois ce partitionnement effectué, le pivot est déjà à sa position finale triée ;
- Trier récursivement les sous-séquences : trier récursivement la sous-séquence des éléments plus petits que le pivot et la sous-séquence des éléments plus grands que le pivot.
Le cas de base de la récursion est lorsque la taille de la séquence est nulle ou un, auquel cas la séquence est évidemment déjà triée.
Il existe plusieurs méthodes spécifiques pour choisir le pivot. Cette méthode de sélection a un impact décisif sur la performance temporelle du tri.
Exemple
def partition(arr,low,high):
i = ( low-1 ) # Indice de l'élément minimum
pivot = arr[high]
for j in range(low , high):
# L'élément actuel est inférieur ou égal au pivot
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# arr[] --> tableau trié
# low --> index de début
# high --> index de fin
# Fonction de tri rapide
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Tableau trié :")
for i in range(n):
print ("%d" %arr[i]),
La sortie de l'exécution du code ci-dessus est :
排序后的数组: 1 5 7 8 9 10Autres extensions