Discussion :

[el toro diablo]

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.

[lgirard]

voici une adresse sympae :

http://ndailly.free.fr/projets/tris/

[Metal Tom]

Faudrait savoir quel type de liste tu utilises. Simplement ou doublement chainées ? Circulaire ? etc.

[el toro diablo]

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).

[ickis]

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

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++; 
			}
		}
 
	}

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 ++.

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...

[lgirard]

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.

[Vincent PETIT]

Tu as aussi le tri à bulle.

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'à

Plus d'info : http://www-ipst.u-strasbg.fr/ipst/deug-ti/aide-c/tris/

[lgirard]

au risque de me répéter, il y a aussi :
http://ndailly.free.fr/projets/tris/

[WOLO Laurent]

Vous trouverez votre bonheur ici

[el toro diablo]

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é) ?

[lgirard]

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.

[WOLO Laurent]

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

[lgirard]

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....

ce n'est pas le seul à disposer de cette complexité

[grishka]

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....

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 optimal

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.

[WOLO Laurent]

Un algo du tri fusion SVP ?

[lgirard]

un algo du tri fusion, avec démonstration de complexité :
http://ndailly.free.fr/projets/tris/fusion.html

[el toro diablo]

merci