Tri rapide en Python
Les valeurs sont séparées en groupes inférieurs, égaux et supérieurs au pivot.
Qu’est-ce que Tri rapide en Python ?
Les valeurs sont séparées en groupes inférieurs, égaux et supérieurs au pivot.
Partitionner les valeurs autour d’un pivot.
Quand l’utiliser ?
- Comprendre les algorithmes et structures de données.
- Observer chaque étape et traiter les cas limites.
- Comparer temps d’exécution et mémoire.
Visualisation de Tri rapide en Python
O(n log n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
main.py
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))Résultat attendu
[1, 5, 7, 8, 9, 10]Fonctionnement
Temps moyen O(n log n), mais O(n²) avec de mauvais pivots.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.