Qu’est-ce que le tri rapide et comment ça marche ? (Avec exemples)
© whiteMocca / Shutterstock.com
Les algorithmes de tri se divisent généralement en deux camps : faciles à mettre en œuvre ou plus rapides à exécuter. Le tri rapide tombe principalement dans cette dernière catégorie. Lisez la suite pour savoir comment implémenter cet algorithme et les meilleures situations pour lesquelles l’utiliser.
Qu’est-ce que le tri rapide ?
Le tri rapide est un algorithme de tri utilisé pour organiser des tableaux de données. Il repose essentiellement sur le principe connu sous le nom de diviser pour mieux régner. C’est la méthode par laquelle nous décomposons un problème plus gros et plus complexe en sous-problèmes plus simples. Ces sous-problèmes sont ensuite résolus et les solutions sont combinées pour trouver la solution au problème initial.
L’algorithme derrière le tri rapide
Ce n’est pas exactement comment implémenter le tri rapide, mais donne une idée de son fonctionnement.
//i -> Starting index, j --> Ending index
Quicksort(array, i, j)
{
if (i < j)
{
pIndex = Partition(A, i, j)
Quicksor(A,i,pIndex-1)
Quicksort(A,pIndex+1, end)
}
}
Tout d’abord, nous définissons le tri rapide comme une fonction d’un tableau avec un élément de départ et un élément de fin. L’instruction « if » vérifie que le tableau contient plus d’un élément.
Dans ce cas, nous appelons la fonction « partition », qui nous donne l’indice de l’élément « pivot ». Cela sépare le tableau en deux sous-tableaux, avec des éléments plus petits et plus grands que le pivot respectivement.
La fonction est appelée récursivement sur chaque sous-tableau, jusqu’à ce que chaque sous-tableau n’ait qu’un seul élément. Le tableau trié est ensuite renvoyé et le processus est terminé.
©Dcoetzee/Domaine Public – Licence
Un exemple de tri rapide
Comme avec la plupart des choses, le tri rapide est mieux expliqué en utilisant un exemple pour illustrer.
Prenons le tableau suivant – [56, 47, 98, 3, 6, 7, 11]
Nous avons des indices de 0 à 6 (rappelez-vous que le premier élément est l’indice 0, pas 1).
En prenant le dernier élément comme pivot, le tableau est réorganisé de sorte que les éléments plus petits que le pivot soient à gauche et les éléments plus grands à droite. Cela se fait en initialisant les variables i et j à 0. Si arr[j]ou l’élément courant, est plus petit que le pivot, on l’échange avec arr[i] et faites-le progressivement. Le pivot est ensuite permuté avec arr[i] afin que cet élément soit dans sa position triée.
Cela donne les sous-tableaux [6, 7, 3] et [56, 47, 98]. L’indice de l’élément pivot est maintenant 3 au lieu de 6.
Le tri rapide est alors appelé, qui trie le sous-tableau de gauche autour de l’élément pivot, 3, en triant les sous-tableaux [6] et [7].
Nous appelons ensuite le tri rapide de manière récursive sur le bon sous-tableau, de sorte qu’il soit trié en [47, 56, 98].
Enfin, les sous-tableaux sont combinés pour donner le tableau trié – [3, 6, 7, 11, 47, 56, 98].
Mise en œuvre
Maintenant que nous avons couvert la base du tri rapide, implémentons-le en utilisant Python. Le code que nous utilisons peut être décrit comme suit :
def partition(arr, start, end):
pivot = arr[end]
i = start - 1
for j in range(start, end):
if arr[j] <= pivot:
i = i + 1
(arr[i], arr[j] = (arr[j], arr[i])
(arr[i + 1], arr[end]) = (arr[end], arr[i + 1])
return i + 1
def quicksort(arr, start, end):
if start < end:
pi = partition(arr, start, end)
quicksort(arr, start, pi - 1)
quicksort(arr, pi + 1, end)
array = [56, 47, 98, 3, 6, 7, 11]
quicksort(array, 0, len(array) - 1)
print(f'Sorted: {array}')
Tout d’abord, nous définissons une fonction de partition en tant que fonction d’un tableau, avec un index de début et de fin.
La valeur pivot est alors définie sur le dernier élément du tableau, et i est initialisé à l’index de départ, moins 1.
La boucle « for » itère sur le tableau, de l’index de départ à l’index de fin moins 1.
L’instruction « if » permute l’élément actuel, j, avec la valeur à l’indice i si j est inférieur ou égal au pivot. La variable i est alors incrémentée.
Après cela, le pivot est permuté avec l’élément à l’indice i+1. Cela signifie que tous les éléments à gauche du pivot lui sont inférieurs ou égaux et que les éléments à droite lui sont supérieurs.
L’index de la valeur pivot est alors renvoyé.
« Quicksort » est alors défini comme une fonction du tableau, et le tableau est vérifié pour s’assurer qu’il a plus d’un élément.
La fonction « partition » est alors appelée, avec la valeur d’index fixée à « pi ». Le tri rapide est appelé de manière récursive sur les sous-tableaux gauche et droit, jusqu’à ce que chaque sous-tableau ne contienne qu’un seul élément.
Enfin, un tableau trié est créé et imprimé à l’aide de la fonction « print ».
©Histoire-Informatique.com
Meilleurs et pires cas d’utilisation du tri rapide
Bien que la théorie du tri rapide puisse sembler compliquée au premier abord, l’algorithme présente de nombreux avantages et est généralement assez rapide. Examinons la complexité temporelle et spatiale du tri rapide.
Complexité temporelle du tri rapide
Le tableau résume la complexité temporelle du tri rapide.
| Cas | Complexité temporelle |
|---|---|
| Meilleur | O (n log n) |
| Moyenne | O (n log n) |
| Pire | Sur2) |
Le meilleur cas est lorsque la partition est équilibrée, où le pivot est proche ou égal à la valeur médiane. Ainsi, les deux sous-réseaux sont de taille similaire et n opérations sont effectuées à chaque niveau. Cela conduit à une complexité temporelle logarithmique.
Lorsque l’élément pivot est relativement proche, c’est le cas moyen. La complexité temporelle est la même que dans le meilleur des cas puisque les tableaux sont à peu près égaux en taille.
Cependant, le pire des cas transforme la complexité temporelle en temps quadratique. En effet, le réseau est très déséquilibré, où le pivot est proche de l’élément minimum ou maximum. Cela provoque une situation dans laquelle les sous-réseaux sont de taille très inégale, l’un d’entre eux ne contenant qu’un seul élément. En tant que tel, il existe n niveaux de récursivité ainsi que n opérations, conduisant à une dépendance quadratique sur la taille d’entrée.
Complexité spatiale du tri rapide
Un autre facteur à considérer est la complexité spatiale du tri rapide. Cela peut se résumer ainsi :
| Cas | Complexité spatiale |
|---|---|
| Meilleur | O (log n) |
| Moyenne | O(log n) |
| Pire | Sur) |
La complexité de l’espace pour le tri rapide est la même pour les meilleurs cas et les cas moyens. En effet, l’algorithme a des niveaux récursifs log n et chaque appel récursif utilise une quantité constante d’espace mémoire. Ainsi, l’espace mémoire total est proportionnel à la profondeur de l’arbre de récursivité.
Dans le pire des cas, cependant, la complexité spatiale est changée en O(n). Parce que l’arbre de récursivité est considérablement déséquilibré, ce qui signifie qu’il y a n appels récursifs.
Emballer
Dans l’ensemble, le tri rapide est, comme son nom l’indique, un moyen très efficace de trier un tableau, en particulier les plus grands. Une fois le processus compris, il est relativement facile à mettre en œuvre et à modifier. Il est utile dans un large éventail de scénarios et constitue une bonne base pour des algorithmes de tri plus complexes.
Suivant…
Qu’est-ce que le tri rapide et comment ça marche ? (Avec exemples) FAQ (Foire aux questions)
Qu’est-ce que le tri rapide ?
Le tri rapide est un algorithme de tri pour trier des tableaux de données. Cela fonctionne en sélectionnant un élément pivot et en divisant le tableau en deux sous-tableaux, un avec des éléments plus petits que le pivot et un avec des éléments plus grands. Ce processus est répété de manière récursive jusqu’à ce que chaque sous-tableau soit trié et ne contienne qu’un seul élément. Les tableaux sont ensuite combinés pour donner un tableau trié.
Le tri rapide est-il un algorithme stable ?
Le tri rapide est généralement un algorithme instable. Cela signifie que l’ordre relatif des éléments égaux peut ne pas être conservé dans la sortie finale.
Comment choisir l’élément pivot avec tri rapide ?
Vous pouvez choisir le premier ou le dernier élément, ou faire un choix aléatoire. Avec des ensembles de données particulièrement volumineux, la randomisation du choix conduit généralement à de bonnes performances.
Quelle est la complexité temporelle du tri rapide ?
Le meilleur cas moyen est O(n log n), tandis que le pire cas est O(n2).
Quelle est la complexité spatiale du tri rapide ?
Le meilleur cas et le cas moyen sont O(log n), tandis que le pire cas est O(n).
Quels sont les meilleurs cas pour utiliser le tri rapide ?
Le tri rapide peut être utilisé pour de nombreux types de tableaux, mais parfois, des alternatives telles que le tri par tas ou le tri par fusion peuvent mieux fonctionner, compte tenu de certaines contraintes. C’est généralement là que vous avez besoin d’un algorithme stable comme le tri par fusion, ou lorsque le temps est un facteur. Par exemple, la complexité temporelle dans le cas le plus défavorable du tri par tas est aussi bonne que la complexité temporelle moyenne dans le cas du tri rapide. Des algorithmes plus simples comme la sélection ou le tri par insertion peuvent également être plus rapides pour les petits ensembles de données.
