je cherche de bons algos de tri de listes (tri par insertion, tri par bulle, tri rapide,...) de faible complexité.
En fait je cherche plus un lien, un tutoriel ou un cours.
je cherche de bons algos de tri de listes (tri par insertion, tri par bulle, tri rapide,...) de faible complexité.
En fait je cherche plus un lien, un tutoriel ou un cours.
voici une adresse sympae :
http://ndailly.free.fr/projets/tris/
Faudrait savoir quel type de liste tu utilises. Simplement ou doublement chainées ? Circulaire ? etc.
Tu te complique la vie, c'est une liste toute bête à une dimension contenant juste des entiers, que je veux classer avec une certaine relation d'ordre simple : <,>,=<, ....
Je voudrais seulemnt un algo pour pouvoir implémenter ma PROPRE fonction de tri. Ddans le langage que j'utilise, des fonctions de tri existent déjà, mais je voudrais simplement implémenter ma/mes fonction(s).
tiens ca c'est un algorytme de tri que j'ai ecris moi meme :
il tri des probabilité par ordre croissant
et elle traite meme les valeurs egales
Le principe c'est que chaque variable triée posséde une position. Tu compare chaque variable a chacune des autres et a chaque fois que tu trouve une variable ayant une valeure superieure, tu fais position ++.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 int position; for (i=1 ; i<proba ; i++) { position=0; for (j=1; j<proba ; j++) { if (tab[i] < tab[j]) { position++; } if ((tab[i]==tab[j]) && (j<i)) { position++; } } }
Ainsi, la variable qui est la plus grande, aura la position 0
la variable ayant une variable superieur a elle aura la position 0 ++ = position 1
etc...
c'est pas réellemetn une découverte, ce tri s'appelle le tri par insertion et est connu depuis fort longtemps.
Cependant, il a le gros avantage d'être extrêment simple à mettre en oeuvre.
Tu as aussi le tri à bulle.
Plus d'info : http://www-ipst.u-strasbg.fr/ipst/deug-ti/aide-c/tris/
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 ok, i, tampon, nbr_item_tableau variable # Faire jusqu'à ce que ok = 1 | | ok <- 1 | i <- 1 | | Faire tant que (i < nbr_item_tableau) par pas de 1 | | | | Si (tableau[i-1] > tableau[i]) alors faire | | | | | | ok <- 0 | | | tampon <- tableau[i-1] | | | tableau[i-1] <- tableau[i] | | | tableau[i] <- tampon | | | | | Fin si | | | Fin faire tant que | Fin faire jusqu'à
au risque de me répéter, il y a aussi :
http://ndailly.free.fr/projets/tris/
Vous trouverez votre bonheur ici
Merci à tous, ça m'a beaucoup aidé, j'ai trouvé ce que je cherchais.
une dernière petite question : lequel est le plus efficace (en terme de complexité) ?
il n'y a pas vraiment de réponse unique, car il faut tenir compte de ce que tu tries, de la quantité à trier, .....
Neanmoins, des éléments de réponse se trouvent également sur ces sites, ils t'indiquerons les complexités théoriques.
Bonne lecture.
Le Tri récursif rapide QuickSort est le meilleur en terme de complexité O(n.log(n)) suivant son algorithme tiré du livre de Sedgewick....
Voici son algorithme
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 Global :Tab[min..max] tableau d'entier fonction Partition( G , D : entier ) résultat : entier Local : i , j , piv , temp : entier début piv <--- Tab[D]; i <--- G-1; j <---D; repeter repeter i <--- i+1 jusquà Tab[i] >= piv; repeter j <--- j-1 jusquà Tab[j] <= piv; temp <--- Tab[i]; Tab[i] <--- Tab[j]; Tab[j] <--- temp jusquà j <= i; Tab[j] <--- Tab[i]; Tab[i] <--- Tab[d]; Tab[d] <--- temp; résultat <--- i FinPartition Algorithme TriRapide( G , D : entier ); Local : i : entier début si D > G alors i <--- Partition( G , D ); TriRapide( G , i-1 ); TriRapide( i+1 , D ); Fsi FinTRiRapide
Envoyé par WOLO Laurent
ce n'est pas le seul à disposer de cette complexité
![]()
n'oublie pas de préciser que c'est la complexité moyenne...la complexité maximale est O(n^2). Car le choix du pivot n'est pas toujours optimalLe Tri récursif rapide QuickSort est le meilleur en terme de complexité O(n.log(n)) suivant son algorithme tiré du livre de Sedgewick....
un des meilleurs tri en terme de complexité max est le tri fusion : O(n.log(n))
La différence entre quicksort et fusion résidant dans la constante multiplicative en faveur du quicksort.
Un algo du tri fusion SVP ?
un algo du tri fusion, avec démonstration de complexité :
http://ndailly.free.fr/projets/tris/fusion.html
merci
Partager