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.
Version imprimable
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22ok, 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:
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
:!: ce n'est pas le seul à disposer de cette complexité :!:Citation:
Envoyé par WOLO Laurent
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 optimalCitation:
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....
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