Discussion :

[master_turc]

ab

[souviron34]

désolé on n'est pas sur www.onfaittesdevoirs.com

Réfléchis, poste-nous ce que tu as fait, et là on t'aidera...

[Sve@r]

Bonjour à tous, j'ai un petit problème concernant la réorganisation d'un vecteur, est ce que quelqu'un peut m'aider svp c'est assez urgent.

Au fait nous avons un vecteur, exemple: 0 -3 7 3 1 -5 -3 2 -1 0 2 0 -6
Le but est de non pas trier ce vecteur mais de rassembler les élements négatifs au début du vecteur suivis des élements nuls et pour finir tous les éléments positifs à la fin du vecteur.
exemple: -3 -5 -3 -1 -6 0 0 0 7 3 1 2 2

Pourriez vous m'aider en m'expliquant l'algorithme qui permet de faire ça mais il y a des contraintes: - Ne pas utiliser un tableau intermédiaire
- L'algorithme ne doit parcourir le vecteur V qu'une
seule fois (donc un tour de boucle!)
remarque: Les élements négatifs,nuls ou positifs ne doivent pas forcément être trié, le but est uniquement de séparer ces 3 sous-groupe.Merci de votre aide

En un seul tour de boucle je ne vois pas. On peut s'en sortir en implémentant un tri à bulle (en considérant qu'un élément négatif est plus petit qu'un élément nul qui lui-même est plus petit qu'un élément positif) mais ça implique quand-même plusieurs tours de boucles.
Ou alors on commence par déterminer la taille de chaque sous-groupe puis on place un pointeur au début de chaque sous-groupe et tout élément du pointeur qui n'est pas à sa bonne place est échangé avec un autre mais ça implique quand-même 2 tours de boucles (un pour compter et un pour permuter)

De toute façon ce n'est pas un pb de C mais un pb d'algo...

[droggo]

Jiu,

Tiens, l'énoncé a changé.

Dans le temps, c'était un tableau de boules de 3 couleurs, il fallait mettre les rouges au début du tableau, puis les blanches, puis les bleues.

C'est possible en un seul tour, il suffit de réfléchir un peu, et peut-être d'écrire sur un papier comment on peut faire ça à la main, en s'imposant de ne jamais revenir en arrière dans le tableau.

[souviron34]

voila ce que j'ai essayé de faire mais ca ne marche pas a tout les coups car jutilise le remplissement aléatoire.si vous pouvez optimiser ce code ce serait sympa de votre part.merci

tu as la réponse ici :

C'est possible en un seul tour, il suffit de réfléchir un peu, et peut-être d'écrire sur un papier comment on peut faire ça à la main, en s'imposant de ne jamais revenir en arrière dans le tableau.

Note : une petite aide : il te faudra 2 variables dernier_zero et dernier-negatif...

[droggo]

Gio,

voila ce que j'ai essayé de faire mais ca ne marche pas a tout les coups car jutilise le remplissement aléatoire.si vous pouvez optimiser ce code ce serait sympa de votre part.merci

Tu veux dire "si vous pouvez corriger ce code ce serait sympa de votre part."

On ne cherche pas à optimiser un code qui ne fonctionne pas.

[diogene]

La question n'est pas si facile à traiter aussi voici une manière d'aborder le problème:

On note la position des éléments du tableau par
- Deb pour le premier élément du tableau
- PNPos pour le premier élément non positif du tableau
- PNeg pour le premier élément négatif du tableau
- Cur pour l'élément en cours d'analyse du tableau
- Fin pour le dernier élément du tableau

- Tous les élements entre [Deb et PNPos[ sont positifs
- Tous les éléments entre [PNPos et PNeg[ sont nuls
- Tous les éléments entre [PNeg et Cur[ sont négatifs
- Les éléments entre [Cur et Fin] n'ont pas été analysés

Schématiquement, on a les deux possibilités suivantes :

Code :

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

1
2
3
4
5
6
7
8
9
  deb      +      |         deb   +
           +      |               +
  PNPos    0      |  PNPos,PNeg   -
           0      |               -
  PNeg     -      |               -
           -      |               -
  Cur      ?      |        Cur    ?
           ?      |               ?
  Fin      ?      |        Fin    ?

- Si l'élément courant est négatif, il est correctement positionné dans la zone des négatifs entre [PNeg et Fin]

- Si il est null, on doit le positionner à la suite de PNeg en fin du bloc de zéro [PNPos et PNeg[. L'élément qui se trouvait en PNeg est négatif et remplacera le zéro dans la zone des négatifs. PNeg doit être mis à jour.
Voici les deux possiblités avec la configuration avant et après :

Code :

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

1
2
3
4
5
6
7
8
9
  deb      +       +            |        deb     +       +
           +       +            |                +       +
  PNPos    0       0    PNPos   | PNPos,PNeg     -x      0   PNPos
           0       0            |                -       -   PNeg
  PNeg     -x      0            |                -       -
           -       -    PNeg    |                -       -
  Cur      0       -x           |        Cur     0       -x
           ?       ?            |                ?       ?
  Fin      ?       ?            |        Fin     ?       ?

- si il est positif, il faut le mettre en fin de zone des positifs [Deb et PNPos[ à la place de l'élément en pNPos. L'élément en PNPos était null ou négatif, on le placera en PNeg, fin de zone des nulls qui est également le début des négatifs. L'élément, négatif, qui était en PNeg va remplacer l'élément courant. PNPos et PNeg sont mis à jour.

Code :

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

1
2
3
4
5
6
7
8
9
  deb      +       +            |        deb    +        +
           +       +            |               +        +
  PNPos    0       +x           | PNPos,PNeg    -y       +x
           0       0    PNPos   |               -        -    PNPos,PNeg
  PNeg     -y      0            |               -        -
           -       -    PNeg    |               -        -
  Cur      +x      -y           |       Cur     +x       -y
           ?       ?            |               ?        ?
  Fin      ?       ?            |       Fin     ?        ?

Il reste à formaliser cette idée sous la forme d'un algorithme. L'algorithme obtenu est très court !

[Sve@r]

Code :

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

1
2
3
4
5
6
7
8
		if(vec[i]==0)
		{
			nul++;
			temp=vec[nul];
			vec[nul]=vec[i];
			vec[nul]=temp;
		}

Il y a un problème sur la partie en rouge de ton code

[PRomu@ld]

Dans le temps, c'était un tableau de boules de 3 couleurs, il fallait mettre les rouges au début du tableau, puis les blanches, puis les bleues.

C'est le problème du drapeau hollandais de Dijkstra, et il s'applique parfaitement ici.

[droggo]

Kio,

C'est le problème du drapeau hollandais de Dijkstra, et il s'applique parfaitement ici.

Je n'ai pas dit le contraire, sinon pourquoi aurais-je rappelé ça ?

D'ailleurs, le problème est plus connu sous le nom de "problème du drapeau tricolore", sans précision de la nationalité du drapeau.
Ce qui ne signifie pas que ta dénomination est fausse, seulement moins courante (ça se trouve, c'est la bonne d'origine, j'ai la flemme de chercher ).