Discussion :

[IDE]

Bonjour à tous, voici un exercice que je dois réaliser :

Un tableau à une dimension contient des entiers égaux à 0, 1 ou 2. Ecrire un algorithme qui range les éléments de ce tableau dans un deuxième tableau de manière que les 0 soient rangés en tête, puis les 1 puis les 2. Le premier tableau ne sera parcouru qu'une seule fois. Il sera initialisé à sa déclaration et affiché

Et voici ma solution, mais je ne sais pas si c'est une bonne chose de l'avoir fait de cette manière, merci pour vos remarques.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
Constante MAX = 6
Tableau entier iTableau taille MAX
<* = {0,0,2,1,2,1} *>
Tableau entier iEchange taille MAX
Variable indice iI
 
Début du traitement
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à 5
 
      Afficher iTableau[iI] Tab
 
   Fin de compter
 
   Fin de ligne
   Fin de ligne
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à 5
 
      /* Alternative : */
      Si iTableau[iI] == 0 Alors
 
	 iEchange[0] <- 0
	 iEchange[1] <- 0 
 
	 /* */
      Sinon
 
	 si iTableau[iI] == 1 Alors
 
	    iEchange[2] <- 1
	    iEchange[3] <- 1 
 
	 Sinon
 
	    si iTableau[iI] == 2 Alors
 
	       iEchange[4] <- 2
	       iEchange[5] <- 2 
 
	    Fin de si
	    Fin de si
      Fin de si
 
   Fin de compter
 
   /* Boucle : */
   Initialisation
   Compter  avec iI de 0 à 5
 
      Afficher iEchange[iI] Tab
 
   Fin de compter
 
  Attente 
 
Fin du traitement

Merci pour votre aide.

Michael

[borisd]

Ton algo ne marche que si tu as deux 0, deux 1 et deux 2. Dans les autres cas, il ne fonctionne pas.

Essaie simplement de faire un programme qui commence par compter le nombre de 0, le nombre de 1, le nombre de 2, puis remplit le tableau de résultat sachant ces nombres.

[Hephaistos007]

Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri

[millie]

Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri

IDE demande explicitement que la complexité soit en O(n). Et non en O(n ln n) ou O(n²) tel un algorithme de tri classique. Par contre, un algorithme de tri comptage fonctionne (mais cela revient à ce que borisd disait)

[j.p.mignot]

en O(n) par exemple :

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
 
 
const n = 25;
var T_initial, T_final : array[0..n-1] of byte;
procedure ordone;
var i : integer; n1, n2 : integer;
   begin
   for i:=0  to n-1 do T_Initial[i]:=Random(3); // ou mettre les data en question
   n1:=-1; 
   n2:=n;
   for i:=0 to n-1 do
   if T_initial[i]=0 then 
      begin 
      inc(n1); 
      T_final[n1]:=0 
      end
   else
   if T_initial[i]=2 then 
      begin 
      dec(n2); 
      T_final[n2]:=2 
      end;
   if n1 < n2-1 then for i:=n1+1 to n2-1 do 
      T_final[i]:=1;
   end;

[IDE]

Merci pour toutes ces réponses, je suis allé sur le suite suivant :

http://fr.wikipedia.org/wiki/Tri_comptage

qui explique se que je voudrais faire mais je ne comprend pas bien l'algorithme, si quelqu'un pourrait me l'expliquer se serait super sympa, merci

Michael