Sauter à un chapitre clé
Les bases de l'algorithme de tri sélectif en Python
Quicksort est un algorithme de tri efficace développé par Tony Hoare en 1959. Il s'agit d'un algorithme de tri par comparaison qui fonctionne selon la technique du diviser-conquérir, ce qui signifie que l'algorithme divise l'entrée en plus petits morceaux, les trie individuellement et combine les morceaux triés pour construire la sortie finale.Le concept principal de Quicksort consiste à choisir un élément pivot dans le tableau et à diviser les autres éléments en deux groupes - l'un avec les éléments inférieurs au pivot et l'autre avec les éléments supérieurs au pivot. Ce processus est effectué de façon récurrente pour les sous-réseaux jusqu'à ce que le tableau entier soit trié.
- Dans le meilleur des cas : \N( O(n\Nlog n) \N)
- Cas moyen : \N( O(n\log n) \N)
- Pire cas : \N( O(n^2) \N)
Application du tri sélectif en Python
Pour mettre en œuvre l'algorithme Quicksort en Python, il est essentiel de se concentrer sur les aspects suivants :- Le choix du pivot
- La fonction de partition
- L'implémentation récursive
Un exemple de mise en œuvre de Quicksort en Python en utilisant le dernier élément de la liste comme pivot :
def quicksort(arr) : if len(arr) <= 1 : return arr pivot = arr.pop() lesser = [] greater = [] for x in arr : if x <= pivot : lesser.append(x) else : greater.append(x) return quicksort(lesser) + [pivot] + quicksort(greater)
Déroulement de l'algorithme Python Quicksort
Le déroulement de l'algorithme de tri sélectif en Python peut être décomposé en plusieurs étapes principales :- Choisis un élément pivot dans la liste.
- Partitionne la liste autour du pivot, de sorte que les éléments inférieurs au pivot soient placés avant le pivot, et que les éléments supérieurs au pivot soient placés après le pivot.
- Applique récursivement l'algorithme de tri sélectif sur les deux sous-réseaux (les éléments plus petits que le pivot et les éléments plus grands que le pivot) jusqu'à ce que tous les tableaux soient triés.
| Tableau : | 5, 3, 8, 4, 2 |
| Pivot : | 2 |
| Tableau partitionné : | [2] | [5, 3, 8, 4] |
| Appel récursif sur le sous-réseau de gauche : | (Rien à trier) |
| Appel récursif sur le sous-réseau de droite : | Quicksort([5, 3, 8, 4]) |
Le tri sélectif est un algorithme de tri sur place, ce qui signifie qu'il ne nécessite pas de mémoire supplémentaire pour le tri. Cependant, l'implémentation récursive montrée ci-dessus ne présente pas une version in-place, car elle crée de nouvelles listes pour le partitionnement. En pratique, Quicksort peut être mis en œuvre pour trier le tableau en place sans avoir besoin de mémoire supplémentaire.
Implémentation du tri sélectif en Python : Exemples
Pour bien comprendre le code de tri sélectif en Python, décomposons la mise en œuvre en une séquence d'étapes. Étape 1 : Choisir un élément pivot- La sélection d'un pivot approprié est cruciale pour l'efficacité de l'algorithme. Les stratégies courantes consistent à sélectionner le premier, le milieu ou le dernier élément, ou à utiliser la médiane de trois éléments (premier, milieu et dernier).
- Ensuite, réorganise le tableau de façon à ce que les éléments plus petits que le pivot soient placés avant lui et que les éléments plus grands que le pivot soient placés après lui. Cette étape est communément appelée "partitionnement".
- Enfin, tu appliques récursivement l'algorithme de tri sélectif sur les deux sous-réseaux (éléments inférieurs au pivot et éléments supérieurs au pivot) jusqu'à ce que le cas de base soit atteint (un tableau vide ou un tableau de taille 1).
Voici un exemple d'implémentation de Quicksort en Python en utilisant le dernier élément comme pivot :
def quicksort(arr) : if len(arr) <= 1 : return arr pivot = arr.pop() lesser = [] greater = [] for x in arr : if x <= pivot : lesser.append(x) else : greater.append(x) return quicksort(lesser) + [pivot] + quicksort(greater)
Implémentation Python du tri sélectif en place
L'implémentation présentée précédemment, bien que valide, n'est pas un algorithme de tri sur place, car elle crée de nouvelles listes pendant le partitionnement. La variante in-place de Quicksort ne nécessite pas de mémoire supplémentaire pendant le processus de tri. Cette section traite de l'implémentation in-place de Quicksort en Python : Étape 1 : Choisir un élément pivot- De manière similaire à l'implémentation précédente, choisis un pivot approprié.
- Crée une fonction de partition qui prend le tableau, un indice de départ et un indice d'arrivée comme arguments d'entrée. Cette fonction réorganisera les éléments autour du pivot et renverra l'index du nouvel emplacement du pivot.
- Définis la fonction qui prend un tableau, un indice de départ et un indice d'arrivée comme arguments d'entrée. Cette fonction effectuera le tri sélectif sur place en appelant la fonction de partition, puis en triant récursivement les sous-réseaux.
:def partition(arr, low, high) : pivot_idx = (low + high) // 2 arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] i = low - 1 for j in range(low, high) :
si arr[j] < pivot : 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_inplace(arr, low, high) : if low < high :
pivot_index = partition(arr, low, high) quicksort_inplace(arr, low, pivot_index - 1) quicksort_inplace(arr, pivot_index + 1, high)Pour utiliser la fonction Quicksort in-place, appelle-la comme ceci :arr = [10, 3, 8, 4, 2] quicksort_inplace(arr, 0, len(arr) - 1)En résumé, comprendre l'implémentation détaillée de l'algorithme Quicksort en Python, en particulier la version in-place, est important pour les étudiants en informatique et les programmeurs en herbe qui veulent améliorer leur compréhension des algorithmes de tri et des techniques efficaces de résolution de problèmes en utilisant Python.
Techniques avancées de tri sélectif
Bien que l'algorithme de tri sélectif traditionnel repose sur la récursivité, il est également possible de mettre en œuvre une version itérative à l'aide d'une pile. L'approche itérative peut s'avérer utile lorsqu'il s'agit de trier des données extrêmement volumineuses, car elle permet d'éviter le risque de se heurter aux limites de profondeur de la récursivité. Cette section se penche sur les détails et les étapes nécessaires à la mise en œuvre d'un algorithme itératif de tri sélectif en Python. Pour commencer, comprenons les principaux composants de l'algorithme de tri sélectif itératif :- Crée une pile pour garder une trace des indices des éléments à trier.
- Tant que la pile n'est pas vide, retire les deux éléments supérieurs (représentant les limites inférieure et supérieure du sous-réseau) de la pile.
- Partitionne le sous-réseau et obtiens l'indice du nouvel emplacement du pivot.
- Repousse les indices des sous-réseaux de gauche et de droite sur la pile en vue d'un partitionnement et d'un tri ultérieurs.
def partition(arr, low, high) : pivot_idx = (low + high) // 2 arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] i = low - 1 for j in range(low, high) : if arr[j] < pivot :
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_iterative(arr) : stack = [(0, len(arr) - 1)] while stack : low, high = stack.pop() if low < high : pivot_index = partition(arr, low, high) stack.append((low, pivot_index - 1)) stack.append((pivot_index + 1, high))Un aspect essentiel de la transformation de l'algorithme Quicksort de récursif à itératif consiste à remplacer les appels récursifs par des opérations sur la pile, ce qui permet de gérer le processus de tri à l'aide d'une pile tout en évitant les débordements de pile qui peuvent se produire lors d'une récursion profonde.Optimisation de l'algorithme de tri sélectif de Python
Plusieurs techniques peuvent être appliquées pour optimiser les performances de l'algorithme de tri sélectif en Python : 1. Choisir une stratégie de sélection de pivot efficace :- Pivot aléatoire : Sélectionne un élément aléatoire de la liste comme pivot. Cela introduit la randomisation dans l'algorithme, ce qui peut permettre d'éviter les pires scénarios.
- Médiane des trois : Choisis la médiane du premier, du milieu et du dernier élément de la liste comme pivot. Cette approche tend à améliorer l'efficacité du partitionnement, ce qui accélère l'algorithme.
- L'utilisation d'une approche hybride dans laquelle tu passes à un algorithme de tri plus simple (par exemple, Insertion Sort) pour les petits sous-réseaux peut éviter les appels récursifs excessifs et améliorer les performances globales.
- Une autre technique d'optimisation des performances consiste à paralléliser l'algorithme en divisant la liste en parties plus petites et en triant chaque partie simultanément en utilisant plusieurs unités de traitement ou threads.
- En identifiant le sous-réseau le plus grand et le plus petit après le partitionnement, tu peux éliminer l'un des appels récursifs en triant d'abord le sous-réseau le plus petit. Cela permet de réduire le nombre d'appels de fonction et les frais généraux associés.
Quicksort Python - Principaux enseignements
Quicksort Python : algorithme de tri efficace basé sur la technique "diviser pour régner" ; fonctionne en sélectionnant un élément pivot et en répartissant les autres éléments en groupes en fonction de leur relation avec le pivot.
Complexité temporelle : Meilleur cas et cas moyen : O(n log n) ; pire cas : O(n^2)
Mise en œuvre du tri sélectif : Code Python qui trie une liste donnée en sélectionnant un pivot, en partitionnant la liste, puis en appliquant récursivement le tri sélectif aux sous-réseaux.
Implémentation Python du tri sélectif sur place : trie le tableau sans mémoire supplémentaire, en utilisant des fonctions pour le partitionnement et le tri récursif basé sur les indices.
Tri sélectif itératif Python : approche alternative du tri sélectif utilisant une pile pour éviter les limitations de profondeur de récursion, particulièrement utile pour trier de grands ensembles de données.
Apprends plus vite avec les 11 fiches sur Quicksort Python
Inscris-toi gratuitement pour accéder à toutes nos fiches.
Questions fréquemment posées en Quicksort Python
À propos de StudySmarter
StudySmarter est une entreprise de technologie éducative mondialement reconnue, offrant une plateforme d'apprentissage holistique conçue pour les étudiants de tous âges et de tous niveaux éducatifs. Notre plateforme fournit un soutien à l'apprentissage pour une large gamme de sujets, y compris les STEM, les sciences sociales et les langues, et aide également les étudiants à réussir divers tests et examens dans le monde entier, tels que le GCSE, le A Level, le SAT, l'ACT, l'Abitur, et plus encore. Nous proposons une bibliothèque étendue de matériels d'apprentissage, y compris des flashcards interactives, des solutions de manuels scolaires complètes et des explications détaillées. La technologie de pointe et les outils que nous fournissons aident les étudiants à créer leurs propres matériels d'apprentissage. Le contenu de StudySmarter est non seulement vérifié par des experts, mais également régulièrement mis à jour pour garantir l'exactitude et la pertinence.
En savoir plus