Table des matières
Ceci est une ancienne révision du document !
Algorithmes de tri
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé (Référence wikipedia).
Les tris sont intéressants du point de vue de l'apprentissage de l'algorithmique.
Tri à bulles
Quicksort
Version récursive de l'algorithme, avec un pivot arbitraire.
- quicksort_01.py
#! /usr/bin/env python # -*- coding: utf-8 -*- """ Code compact de la fonction quicksort. Exemple de tri d'éléments entiers. """ def quicksort(li): if li == []: return [] pivot = li[0] equal = [pivot] lesser = quicksort([x for x in li[1:] if x <= pivot]) # si x < pivot : élimination des doublons greater = quicksort([x for x in li[1:] if x > pivot]) return lesser + equal + greater from numpy import random a=random.randint(0,1000,10) print(a,len(a)) b=quicksort(a) print(b,len(b))
On peut aussi rendre la fonction encore plus compacte, mais moins lisible :
... def quicksort(li): if li == []: return [] pivot = li[0] return quicksort([x for x in li[1:] if x <= pivot]) + [pivot] + quicksort([x for x in li[1:] if x > pivot]) ...
Références :
Comparaison des tris
L'efficacité des tris peut être comparée suivant la configuration des données initiales (avant tri) et leur nombre. Voir par exemple sur le site www.sorting-algorithms.com, ou cette vidéo :
Cf. aussi cette autre visualisation : Sorting Algorithms Visualized in Python, Using Python 3 and Scikit-Image
Références
- Sources de codes (qualité à vérifier) https://github.com/thecodershub/algorithms/tree/master/python/sort
- Sorting Algorithms in Python Santiago Valdarrama, Real Python