2 minutes
Tri Rapide Avec Python
Dernière mise à jour: 2 octobre, 2022Le tri rapide est un autre algorithme de division et de conquête que nous pouvons utiliser pour trier nos tableaux/listes. Tout d'abord, nous choisissons un point de pivot. Après avoir choisi ce point de pivot (ou valeur), nous mettrons les plus petites valeurs à sa gauche et les plus grandes à sa droite. Nous allons diviser notre tableau/liste par ce point pivot et appeler notre algorithme de tri de manière récursive jusqu'à ce que nous ayons trié la liste.
§Nous Commencerons
Nous pouvons choisir le point de pivot de plusieurs façons. Nous pouvons choisir la première, la dernière ou la valeur médiane comme pivot. Nous pouvons aussi choisir au hasard dans notre liste. Choisir le pivot n'aura pas beaucoup d'importance dans nos exemples, mais à l'avenir, afin d'éviter la complexité temporelle du pire cas, choisissez le milieu comme pivot. Si vous voulez en savoir plus sur l'analyse, allez-y et regardez cette vidéo géniale sur l'analyse de cet algorithme.
§Première Approche
Comme je viens de le dire, il existe plusieurs façons de créer la même fonctionnalité et je vais en montrer 2 ici dans ce post. Dans l'un des algorithmes, nous aurons deux index qui parcourront le tableau. Ils commenceront à différentes extrémités du réseau. L'un cherchera une valeur inférieure au pivot l'autre cherchera une valeur supérieure au pivot. Dans les deux exemples, nous allons trier les tableaux par ordre croissant (min à max).
Voici le code de la première approche :
def partition(arr, low, high):
pivot = arr[high]
l = low
h = high - 1
while True:
while l <= h and arr[h] >= pivot:
h = h - 1
while l <= h and arr[l] <= pivot:
l = l + 1
if l <= h:
arr[l], arr[h] = arr[h], arr[l]
else:
break
arr[high], arr[l] = arr[l], arr[high]
return h
def quick_sort(arr, l, h):
if l < h:
p = partition(arr, l, h)
quick_sort(arr, l, p)
quick_sort(arr, p + 1, h)
if __name__ == "__main__":
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quick_sort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§Deuxième Approche
Dans la deuxième façon que j'aime créer, le même algorithme est en fait beaucoup plus populaire que le premier. Dans celui-ci, nous choisissons la dernière valeur comme pivot. Il y a deux index qui rechercheront une valeur plus grande et plus petite que le pivot. Nous parcourrons le tableau à la recherche d'une valeur inférieure au pivot et lorsque nous la trouverons, nous incrémenterons le deuxième index et les échangerons. Lorsque nous avons terminé l'itération, nous en restons un dans le tableau et la valeur est inférieure à l'index et renvoyons la valeur échangée.
Voici le code de la deuxième approche :
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
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
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§Complexité du Tri Rapide
La complexité temporelle dans le pire des cas pour cet algorithme est O(N²) mais tant que vous n'avez pas de tableau trié, vous ne le verrez pas. Pour éviter d'avoir le pire des cas O(N²), choisissez le pivot comme médian, aléatoire ou comme milieu. La complexité temporelle moyenne sera O(NlogN). N de l'itération du tableau et logn pour diviser le tableau en tableaux plus petits à trier. Je vous suggère de regarder cette vidéo car je pense que c'est l'explication la plus simple et la plus compréhensible que j'ai pu trouver.
Chaque appel récursif utilisera O(1). Comme nous n'utilisons aucun tableau auxiliaire, etc. pour cet algorithme, notre complexité spatiale dépendra de la hauteur de l'arbre créé par les récursions. On peut donc dire que c'est au moins logn. Dans le pire des cas, nous créerons autant de piles que la longueur du tableau. Dans le pire des cas, la complexité spatiale sera O(N). Ce pire cas est également expliqué plus en détail dans la vidéo pour laquelle j'ai laissé le lien juste au-dessus.
Continuez à apprendre!
Ilker AkbiyikArticles Similaires
