Discussion :

[goaks]

Salut, j'aimerai savoir comment faire pour trier un tableau de valeurs dans l'ordre croissant car je ne vois pas comment un algorithme peut faire cela ? Merci.

[droggo]

Hia,

Un algorithme peut faire ça quand c'est un algorithme de tri.

Google et/ou Wikipedia te donneront des tas de réponses en une petite fraction de seconde.

[LadyWasky]

il y a plusieurs algorithmes de tris existant.

Mon préféré, c'est celui qu'on appelle le tri de shell (enfin, on m'a toujours dis qu'il s'appelais comme ça).

Même si ce n'est pas le plus performant, il à le mérite d'ètre déjà très performant en restant très simple :

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
 
//c'est du simili pascal
N : nombre d'éléments d'un tableau
var i,j:entiers;
     Tableau : Tableau d'entiers indicés de 0 à N-1;
     Temp:entier; //variable temporaire
begin
  for i:=0 to N-2 do                 //on fait varier i de 0 à N-2
    for j:=N-1 downto (i+1) do   //on fait varier j de N-1 à (i+1)
      if Tableau[j]<Tableau[i] then  
      begin
        temp:=Tableau[i];
        Tableau[i]:=Tableau[j];
        Tableau[j]:=temp;
      end;
end;

C'est pratiquement le même code que le tri à bulle. A ala différence du tri à bulle, dans celui-ci, la variable j par de la fin du tableau, pas encore triée pour remonter vers ce qui est déjà trier (dans le tri à bulle, avec j, on descend le tableau pour faire remonter les "bulles").

l'algo que je viens de te donner va trier par ordre croissant, pour trier par ordre décroissant il s'agit juste de changer le signe de l'égalité.
Après, pour comprendre comment ça marche, tu te fais un tableau à la main, avec 10 cases que tu remplies de chiffre au hasard, et tu suis le code à la main... et voilà...

[Gwylom]

waskol, j'ai l'impression que ton tri ressemble plus à un tri sélection (ou tri par extraction, c'est le même) qu'à un tri shell.

Mais le fait de partir les éléments de j depuis la fin vers i est plutôt élégant, puisque ça permet de trier quelques éléments de la fin du tableau, alors qu'en parcourant dans l'autre sens, comme c'est le cas dans la version que je connais de ce tri, on les tri dans le mauvais ordre. Alors que le pire des cas pour cet algo est que le tableau soit exactement trié dans le mauvais ordre...

De mon coté j'aime bien le tri fusion, il est joli Pas la peine de donner des détails ici, google est super fort en détails...

[FabaCoeur]

Voila ce que je pourrais apporter en matière d'algorithme de tri:

1) J'utilise tout le temps le tri par selection, car il a le mérite d'être simple à programmer et à retenir. Il a une complexité de a peu près O(n²). Le voila:

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
29
donnée *tab[n];
entier i,j,min;
donnée temp;
 
 
// Parcours du tableau
pour i allant de 0 à n, i+1
faire
 
	min <- i
 
	// Parcours d'un sous tableau
	pour j allant de i+1 à n, i+1
	faire
 
		si tab[j] < tab[min]
		faire
			// On garde l'indice du minimum du sous tableau
			min <- j
		fsi
 
	fpour
 
	// On inverse le minimum avec le 1er element du sous tableau
	temp <- tab[min]
	tab[min] <- tab[j]
	tab[j] <- temp
 
fpour

2) Le "quicksort" est un des tris les plus performant. En revanche, il est loin d'être le plus simple (ni à retenir, ni à programmer) car il utilise plusieurs fonctions avec des appels récursifs.

3) Le tri bulle est à bannir d'après moi, il est vraiment l'un des moins performant, de plus je le trouve encore moins simple que le tri par selection...!

4) Il existe bien d'autre tris (par insertion, ect)...

[ol9245]

Vos considérations sur la difficulté à programmer un quicksort me laissent perplexe. Qui préfère se palucher un algo de tri (polynomial) à la main au lieu de copier/coller un algo réputé (et quasi linéaire) et qui marche sans passage par la case debug ?

J'ai lu Sedgewick avec délices. 10 ans après son bouquin est encore sur mon bureau ! Pourtant, je trouverais baroque de bidouiller moi même un seul de ses algos.

Il n'y a qu'à la fête des mères que les femmes portent des coliers en nouilles fabriqués par leurs gamins. Sedgewick (et les autres) fabriquent des bijoux ? je les porte ! Chacun son métier.

Et si un de mes gars joue à réinventer la roue (de secours, la polynomiale, justement), je lui demande gentilement de s'amuser à ça le soir si ça lui plait. Aux heures de bureau, il est prié d'utiliser Google.