besoin d'une correction sur un exercice.

**phakso** · 02/03/2006, 13h38

Ecrire un algorithme qui permet de saisir un tableau de 20 entiers et qui le trie en ordre croissant et en ordre décroissant à partir d’une position fixée donnée par l’utilisateur.

Une fois le tableau saisi, l’utilisateur fixe la position, avant laquelle le tableau est trié en ordre croissant et après laquelle le tableau est trié en ordre décroissant.

Déclaration :

Var_position
Var Tab tt[20] : tableau d’entiers
T[1]
T[2]
T[3]
T[4]
T[5]
T[6]
T[7]
T[8]
T[9]
T[10]
... jusqu'a T[20]

PRODECURE Tri_bulle (Tableau a[1:n])

VARIABLE permut : Booleen;

REPETER
permut = FAUX
POUR i VARIANT DE 1 à N-1 FAIRE
SI a[i] > a[i+1] ALORS
echanger a[i] et a[i+1]
permut = VRAI
FIN SI position=var_position
FIN POUR
TANT QUE permut = VRAI

FIN PROCEDURE

PRODECURE Tri_bulle_inverse (Tableau a[1:n])

VARIABLE permut : Booleen;

REPETER
permut = FAUX
POUR i VARIANT DE 1 à N-1 FAIRE
SI a[i] > a[i-1] ALORS
echanger a[i] et a[i-1]
permut = VRAI
FIN SI position=20
FIN POUR
TANT QUE permut = VRAI

FIN PROCEDURE

voila, est ce correct ?

**Marco85** · 02/03/2006, 13h51

Envoyé par phakso

PRODECURE Tri_bulle (Tableau a[1:n])
<...>
FIN PROCEDURE

PRODECURE Tri_bulle_inverse (Tableau a[1:n])
<...>
FIN PROCEDURE

Ah bon ?

Marco85

**phakso** · 02/03/2006, 16h07

oui, escuse moi.

PRODECURE Tri_bulle (Tableau a[1:n])
<...>
FIN PROCEDURE

PRODECURE Tri_bulle_inverse (Tableau a[Var_position :n])
<...>
FIN PROCEDURE

**Betatesteur** · 02/03/2006, 16h10

lol chui d'accord avec Marco

Définis plutôt une procédure, inverserTableau, qui change de place les éléments de ce tableau de telle façon que le nouveau tableau soit une sorte de « miroir » de l'ancien.

Exemple : 1 2 4 6 -> 6 4 2 1
c'est assez simple

**ToTo13** · 02/03/2006, 19h09

Bonjour,
une méthode peut etre plus facile que le tri à bulle est tout simplement la recherche qu plus petit ou plus grand élément. Tu cherches le plus petit (grand), tu le met en premier, puis tu continues

**phakso** · 02/03/2006, 21h20

ça donne quoi concrétement ?

Si i supérieur aux autres valeurs mettre i en premier

Je débute. c'est n'importe quoi ce que j'ai écris...

Quand tu parles de tri de recherche, qu'est ce que tu désigne par là ? parce qu'en algorithme de tri, ce que j'ai trouver c'est ça :

Les tris

* Généralités sur les tris
* Tris itératifs
o Généralités sur les tris itératifs
o Tris par sélection
+ Tri par minimum successifs
+ Tri à bulles
o Tri par insertion
* Tris récursifs
o Tri rapide
o Tri par fusion

**phakso** · 02/03/2006, 22h10

je peux utiliser ça !

Principe du tri par sélection

Le principe du tri par sélection est très simple : on parcourt le tableau de la première à la dernière case. Pour chacune des cases, on place le nombre qui y correspond.

Comment ? Au début, on place le plus petit élément dans la première case. Il ne nous reste plus qu'à trier le reste du tableau, de la case 2 à la case n. On place alors le plus petit élément dans la deuxième case. Les deux premières cases sont triées, on trie alors le reste du tableau, de la case 3 à la case n, et ainsi de suite. Ainsi :

Pour i allant de 1 à n, on place le minimum de t[i..n] en t[i]

**phakso** · 02/03/2006, 23h38

Envoyé par Betatesteur

lol chui d'accord avec Marco

Définis plutôt une procédure, inverserTableau, qui change de place les éléments de ce tableau de telle façon que le nouveau tableau soit une sorte de « miroir » de l'ancien.

Exemple : 1 2 4 6 -> 6 4 2 1
c'est assez simple

Oui, mais si l'utilisateur saisie la position 4 comme position d'inversion du sens de tri ?

**phakso** · 03/03/2006, 00h35

Déclaration :
//position d'inversement de l'algo.
Var_position

Var Tab tt[20] : tableau d’entiers
T[1]
T[2]
T[3]
T[4]
T[5]
T[6]
T[7]
T[8]
T[9]
T[10]
... jusqu'a T[20]

Pour i allant de 1 à n :

* on recherche séquentiellement le minimum dans t[i..n],
* on échange t[i] et le minimum.

Donc pour le décroissant, ça devient

Pour i allant de var_position à n :

* on recherche séquentiellement le maximum dans t[i..n],
* on échange t[i] et le maximum.

Il me semble avoir bon maintenant !

**Graffito** · 03/03/2006, 09h10

Bonjour,

Supposons que le nombre d'élément du tableau est N et la position du max est P.
Exemple : N=9 P=6
Il suffit de trier en ordre croissant par un algo classique.
Exemple : 0 1 2 4 7 8 8 9 9
On prend les P-1 premiers nombres et on les déplace en fin de tableau,
Exemple : 4 7 8 8 9 9 0 1 2
On fait une symétrie sur les P-1 derniers nombres par rapport à la position (N-P+1)/2 / cette étape peut bien sûr être couplée à la précédente /.
Exemple : 4 7 8 8 9 9 2 1 0
Ceci ne fournit qu'un des multiples ordre de tri répondant au problème.

**ToTo13** · 03/03/2006, 09h25

Bonjour,
petit complément pour ce que j'ai marqué au début.
Supposons que tu dois trier le tableau à la main de maniére croissante, comment t'y prendais tu ?
Pour moi, je chercherai le plus petit élément et je le mettrai dans la première case. Ensuite je regarderai de la deuxième case à la dernière (plus besoin de regrader la première car elle contient le plus petit élément) et je rechercherai encore le plus petit que je mettrai en deuxième position. Et ainsi de suite.

Donc :
Pour i qui va de 0 < n-1
Pour j qui va de 1 < n
Trouver le plus petit élément et noter ca position.
Inverser la position du plus petit avec l'élement dans la case i.

Voilà c'est tout.

**Betatesteur** · 03/03/2006, 09h33

Toto13, relis bien son énoncé

qui le trie en ordre croissant et en ordre décroissant à partir d’une position fixée donnée par l’utilisateur.

toi tu fais un tris normale. c'est pas ce qu'il veut. en plus il a déjà sa réponse, non?

**ToTo13** · 03/03/2006, 09h49

Oups effectivement, autant pour moi.

Donc on reprend en modifiant ce que j'ai marqué au dessus :

Code :

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

1
2
3
4
5
 
Pour i qui va de Debut < n-1
     Pour j qui va de Debut+1 < n
          Trouver le plus petit élément et noter ca position.
          Inverser la position du plus petit avec l'élement dans la case i.

Donc maintenant ca tri à partir de l'élement Début.

**Betatesteur** · 03/03/2006, 10h01

Envoyé par phakso

Envoyé par Betatesteur

lol chui d'accord avec Marco

Définis plutôt une procédure, inverserTableau, qui change de place les éléments de ce tableau de telle façon que le nouveau tableau soit une sorte de « miroir » de l'ancien.

Exemple : 1 2 4 6 -> 6 4 2 1
c'est assez simple

Oui, mais si l'utilisateur saisie la position 4 comme position d'inversion du sens de tri ?

c'est exactement ça.
1. tris normale
2. l'utilisateur choisi tab[2] par exemple comme point d'inversion du table
3 dans ta boucle tu pars de tab[2] j'usqu'à tab[n] et t'appelle la procédure inverserTableau , fin de ta boucle.
4. t'aura , une partie en ordre croissant et à partir du point d'iversion choisi , le tableau est inversé, ça décrémente.

voilà c'est tout.

besoin d'une correction sur un exercice.

Algorithmes et structures de données

Discussions similaires

Partager

Partager