« Programmation algorithmique/Tris » : différence entre les versions
Contenu supprimé Contenu ajouté
→Tri par sélection : supression pour cause de doublon dans la page |
→Tri rapide : mise en forme de l'algo + ajout d'infos |
||
Ligne 61 :
FONCTION Partitionner ( A : tableau [1..n]
Début
Fin si
Fin tant que
Fin
PROCÉDURE Tri_rapide(A : tableau [1..n], p : entier, r : entier)
Début
Si p < r
q := Partitionner(A,p,r)
Tri_rapide(A,p,q)
Tri_rapide(A,q+1,r)
Fsi
Fin
*'''Complexité en espace :''' En raison des appels récursif, on a besoin d'une pile dont la taille est en <math>O(log(n))</math>.
*'''Complexité en temps :''' <math> O(n.log(n))</math> en moyenne, <math> O(n^{2})</math> dans le pire cas.
*'''Nom anglais :''' ''quicksort''.
=== Tri par base ===
| |||