TP Intégration Continue
Exemple de documentation déployée avec Gitlab
Comparaison des performances de plusieurs algorithmes de tri écrit en Python
tri par selection
tri par selection récursif
tri par insertion
tri fusion
tri bulle
tri rapide
- author
cyril
- copyright
cnrs
- tri.tri_selection(tab, longueur)
Tri par sélection
On détermine la position du plus petit élément, on le met en première position et on itère le procédé sur le tableau restant.
Complexité en 0(lgn2) dans tous les cas.
- Parameters
tab (array) – tableau à trier
longueur – taille du tableau
- Returns
tableau trié
- Return type
array
- tri.tri_recursif(tab, longueur)
Tri par sélection récursif
On détermine la position du plus grand élément et on le met en dernière position. On réappelle alors la fonction tri_recursif sur le sous tableau composé des n-1 premiers éléments de t.
Complexité en O(n**2) dans tous les cas.
- Parameters
tab (array) – tableau à trier
longueur – taille du tableau
- Returns
tableau trié
- Return type
array
- tri.tri_insertion(tab, longueur)
Tri par insertion
On ordonne les deux premiers éléments.
On insère le 3ème de manière à ce que les 3 soient ordonnés.
On insère le i-ème de manière à ce que les i éléments soient ordonnées.
La complèxité est en O(n**2) dans le pire des cas.
- Parameters
tab (array) – tableau à trier
longueur – taille du tableau
- Returns
tableau trié
- Return type
array
- tri.tri_fusion(tab, longueur)
Tri fusion
On découpe le tableau à trier en deux sous-tableaux de taille n/2. On trie alors les deux sous-tableaux récursivement, ou on ne fait rien s’ils sont de taille 1.
On reconstitue le tableau trié initial en fusionnant les deux sous-tableaux triés.
La complexité est en O(n*log(n)) dans le pire des cas.
- Parameters
tab (array) – tableau à trier
longueur – taille du tableau
- Returns
tableau trié
- Return type
array
- tri.tri_bulle(tab, longueur)
Tri bulle
On compare les couples d’éléments successifs pour placer systématiquement le plus grand après le plus petit. Un parcours complet du tableau selon ce processus nous assure que le plus grand élément est en dernière position.
On réitère alors le processus sur le sous tableau restant.
Complexité en O(n**2).
- param tab
tableau à trier
- type tab
array
- param longueur
taille du tableau
- return
tableau trié
- rtype
array
- tri.tri_rapide(tab, longueur)
Tri rapide
On choisit un élément du tableau au hasard qui sera ‘pivot’ et on permute tous les éléments de manière à placer à gauche du pivot les éléments qui lui sont inférieurs, et à droite ceux qui lui sont supérieurs.
On trie alors de la meme manière les deux moitiés de part et d’autre du pivot.
Complexité en O(nlog(n)).
- Parameters
tab (array) – tableau à trier
longueur – taille du tableau
- Returns
tableau trié
- Return type
array