Discussion :

[emna1987]

Ecrire un algorithme qui réarrange les éléments du tableau T de telle façcon que tous les nombres nuls apparaissent au début,suivis des nombres positifs, puis des nombres négatifs.L'algorithme ne doit parcourir le tableau T qu'une seule fois et ne doit pas utiliser de tableau intermédiaires.
j'ai pas trouvé une idée pour cet exercice

[Invité]

salut,

un peu relou mais...
tu peux considérer trois intervalles I_0, I_n, I_p (respectivement contenant nuls, négatifs et positifs)
chacun de ces intervalles est représenté par une taille resp t_0, t_n, t_p (si taille == 0, signifie l'intervalle est vide)
(donc tu stockes pas les valeurs dans les intervalles mais tu te sers des tailles pour mettre à jour le tableau au fur et à mesure que tu avances en calculant les index respectifs)

pour chaque el du tableau
si el==0
tu place el à la taille de t_0.
tu mets à jour t_0
vu que t'ecrases un element (qui par def n'est pas nul) alors il faut bouger cet el
si cet el est negatif, alors tu le mets à t_0+t_1
donc faut mettre à jour t_1 et bouger eventuellement lelem que t'écrases
....

c'est relou car il faut être précis sur les indices..

[Flodelarab]

Bonjour

chacun de ces intervalles est représenté par une taille resp t_0, t_n, t_p

Tu ne connais aucune de ces tailles. À moins de parcourir deux fois le tableau. Ce qui est interdit.
La vérité est ailleurs

[Invité]

hello Flodelarab,

je suis vraisemblablement pas assez clair.
l'intervalle est représenté virtuellement (pour comprendre ce qui se passe)
mais concrètement il suffit de trois variables t0,t1,t2 représentant le nombre de fois qu'on a trouvé resp nul, négatif, positif.

un seul parcours de tableau suffit cf pseudo code (qui n'est pas exacte mais qui devrait suffire pour intuiter l'algorithme)
A chaque itération, on ecrit au minimum 0 fois si le tableau est déjà trié (même sil faut mettre à jour le t_{0,1,2} correspondant) et au plus trois fois (si le lelement qu'on place en t0 ecrase un el négatif (qu'il faut déplacer en t0+t1-1) et que lel remplacé est positif (qu'il faut als déplacer en t0+t1+t2-1)

[tatayo]

Bonjour,
Une idée, en vrac: tu parcours le tableau, si tu tombes sur un null tu le mets en première position, si tu tombes sur un positif tu le mets en dernière position, sinon tu ne fais rien.
Au final tu dois retrouver les null en premier, les positif en dernier et les négatifs vont naturellement finir au milieu.
Il y a peut-être une subtilité dans la gestion du "pointeur". Mais comme il s'agit d'un exercice, je ne te donnes pas la solution complète…

Tatayo.

[mach1974]

Pour l'exercercice il faut faire un tri à bulle de complexité o n ln n . Tu parcoures une fois le tableau en trouvant le max sur la moitié de la liste et tu Swap le max dans la cellule precedente avec le suivant

[wiwaxia]

Bonjour,

Ecrire un algorithme qui réarrange les éléments du tableau T de telle façcon que tous les nombres nuls apparaissent au début,suivis des nombres positifs, puis des nombres négatifs.
L'algorithme ne doit parcourir le tableau T qu'une seule fois et ne doit pas utiliser de tableau intermédiaires ...

La condition imposée du parcours unique constitue la grosse difficulté. Elle peut être contournée en définissant un nombre suffisant d'indices auxiliaires.

Soit donc le tableau de (N) termes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

VAR Liste: ARRAY[1..N] OF Type_Nombre;

Il est possible:
a) que le tableau commence une suite ininterrompue de (Iz) termes nuls, et
b) qu'il s'achève par une autre suite ininterrompue de (In) termes négatifs,
ce que l'on repère aisément par des instructions du type:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Iz:= 0;
WHILE (Liste[Iz+1]=0) DO Inc(Iz);
k:= N + 1;
WHILE (Liste[k-1]<0)DO Dec(k);
In:= N + 1 - k;

Il est encore possible (soyons optimistes) que l'on trouve ensuite:
c) une suite ininterrompue de (Ip1) termes positifs succédant aux termes nuls, et
d) une suite analogue de (Ip2) termes positifs précédant les termes négatifs,
ce que l'on trouvera facilement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
k:= Iz;
WHILE (Liste[k+1]>0) DO Inc(k);
Ip1:= k - Iz;
k:= N + 1 - In;
WHILE (Liste[k-1]>0) DO Dec(k);
Ip2:= N + 1 - In - k;

On a ainsi parcouru une fois - et une seule - un certain nombre de termes du tableau (N1 = Iz + Ip1 + Ip2 + In), situés aux deux extrémités de la liste (à moins évidemment qu'ils ne soient tous nuls: N1 >= 0).
Reste à traiter les (N - N1) termes restants, dont les positions vont de (Iz + Ip1 + 1) à (N - In - Ip2).

Cela doit pouvoir se traiter par des transferts de 2 termes, et variation des indices précédents, jusqu'à ce que l'on obtienne (condition d'arrêt):
N = Iz + Ip1 + Ip2 + In .

[Invité]

je ne sais pas ce qui définit "la" bonne piste mais voici la variante que je proposais au début...
pr rappel les intervalles sont stackés de gauche à droite.

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
 
    n taille du tableau
    v le tableau
    pour i=0,i<n,++i
        el = v[i]
 
        si el==0
            ind=i0
            tmp=v[ind]  //element qu'on va ecraser
            v[ind] = el //on ajoute lelement a la fin de notre intervalle virtuel
            i0++
 
            si ind == i
                //on a placé lelement courant à sa place
                //a noter que ca correspond au cas ou le tableau commence par des el nuls.
                //on peut y sortir de la boucle...
                continuer
            finsi
            si tmp == 1
                ind = i0+i1-1   //on retranche -1 car i0+i1 représente l'élement suivant de I1 SAUF que i1 ne change pas taille donc on accède au dernier et non au suivant
                tmp2 = v[ind]    //element qu'on va ecraser
                v[ind] = tmp   //de même on n'incremente pas i1 car l'intervalle n'a toujours pas changé de taille. On a juste fait une "rotation par la gauche"
 
                si ind == i
                    //comme à gauche de i nous sommes tjs triés
                    //c'est "equivalent" à avoir permuté lelem courant qqpart à gauche et on peut arrêter la réflexion
                    //sinon ca signifie qu'on a rembourré lelem 0 au début de I1 et que le début de I1 s'est retrouvé dans lelem courant
                    //et on peut s'arrêter :)
                    continuer
                finsi
 
                ind = i0+i1+i2-1 //meme raison.
                v[ind] = tmp2 //ya pas d'autres intervalles apres i2...
            sinon //le terme à déplacer positif
 
                ind = i0+i1+i2-1
                v[ind] = tmp
 
            finsi
 
        sinon si el==1
            ...
        sinon
            ...
        finsi
    finpour

[tbc92]

Le code correspondant à ce que Tatayo proposait :

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
 
Constantes 
  DEBUT
  MILIEU
  FIN_TABLEAU
fin
nb_lignes_a_traiter est un entier  // = taille du tableau
ligne_a_traiter est un entier = 0
nb_lignes_traitees est un entier = 0
tantque nb_lignes_traitees < nb_lignes_a_traiter
   destination = quelle_destination( tb[ligne_a_traiter] )  //  renvoie un nombre égal à DEBUT , MILIEU ou FIN_TABLEAU    // renvoie DEBUT si tb[xxx] est nul, MILIEU si tb[xxx] est négatif , et FIN_TABLEAU sinon
   selon destination
      cas DEBUT 
            permute ( tb, 0, ligne_a_traiter)
            ligne_a_traiter ++
      cas MILIEU
            // rien à faire
            ligne_a_traiter ++
      cas FIN_TABLEAU
            permute ( tb, nb_lignes_a_traiter -1, ligne_a_traiter )
            // et je n'incrémente pas ligne_a_traiter.
   fin selon
   nb_lignes_traitees++
fin tantque