Quicksort Python

Application du tri sélectif en Python

1. Le choix du pivot
2. La fonction de partition
3. L'implémentation récursive

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

1. Choisis un élément pivot dans la liste.
2. 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.
3. 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.

Implémentation du tri sélectif en Python : Exemples

• 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).

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

• 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)

arr = [10, 3, 8, 4, 2] quicksort_inplace(arr, 0, len(arr) - 1)

Techniques avancées de tri sélectif

1. Crée une pile pour garder une trace des indices des éléments à trier.
2. 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.
3. Partitionne le sous-réseau et obtiens l'indice du nouvel emplacement du pivot.
4. 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))

Optimisation de l'algorithme de tri sélectif de Python

• 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.