Algo tri tableau

**goldy91** · 31/12/2008, 21h33

Bonjour,j'arrive pas a faire cette exercice sur feuille dont voici l'énoncé :
Écrire une fonction permettant de trier un tableau de 10 cases en ordre croissant.Aucune saisie et aucun affichage n'a lieu dans la fonction.Cette fonction prend en paramètre le tableau non trié et rendre le tableau trié .
Merci de votre aide s'il vous plait.

**Frifron** · 01/01/2009, 02h08

salut,

une recherche google avec "algo tri" te donne ca : http://lwh.free.fr/pages/algo/tri/tri.htm...

**Jimalexp** · 01/01/2009, 03h54

Il y a différents algorithmes de tri mais, si tu as le temps, ce serais intéressant pour toi d'élaborer ton proper algorithme.

Quand tu auras mis au point ta propre fonction (et surtout t'habituer à réflêchir à ce genre de problème) tu pourras comparer ca avec les algorithmes les plus courants et comparer les performances en calculant la différence de temps consommé.

Une approche c'est de rechercher la plus grande et la plus petite valeur. Avec ca et quelques variables, il y a déjà moyen de faire un tri.

P.S: Est-ce que l'exercice dois être en C ou en pseudocode ?

**goldy91** · 01/01/2009, 13h25

Merci mais j'ai déjà essayé et je comprend rien donc un soluce svp !!
Pour ce qui est du site c'est pareil je comprend rien ce que je veux c'est la soluce la plus simple.
Je dois faire ce code a l'écrit genre :
Fonction...
Var ..
Debut
....
....
Fin

**pseudocode** · 01/01/2009, 14h00

Envoyé par goldy91

Merci mais j'ai déjà essayé et je comprend rien donc un soluce svp !!
Pour ce qui est du site c'est pareil je comprend rien ce que je veux c'est la soluce la plus simple.

Règles du forum (extrait de la règle 4.13):

4.13 Nous ne sommes pas là non plus pour faire vos exercices.

Entendez par là que nous serons bien évidemment tout à fait d'accord de vous aider à résoudre votre problème, pour autant que vous fassiez vous-même des efforts.

Postez votre question, mais proposez également un début de solution, un bout de code, etc. En aucun cas, nous ne ferons le travail à votre place.

**goldy91** · 01/01/2009, 16h29

D'accord pas de problème mais justement j'arrive pas a comprendre on peut faire le contraire on peut m'aider et je peux a mon tour essayer !!!

**FR119492** · 01/01/2009, 17h05

Salut!
Une bonne approche pour ce genre de problèmes consiste souvent à traiter un petit cas à la main. Alors, tire au hasard le contenu d'un petit tableau et trie le à la main. Comme ça, tu sauras ce que ton programme doit faire.
Jean-Marc Blanc

**Jimalexp** · 01/01/2009, 23h58

En pseudocode donc. Ca ne devrais pas être trop difficile. D'ailleurs commencons avec une liste de dix nombres :

102, 30, -1, 5, 73, 52, 12, 10000, -10, 8

Ensuite il faut un tableau pour stocker tout ca. Appelons le tab.

Pour parcourir le tableau, il faudrais une variable. Appelons la indice. Pour aller chercher une valeur dans le tableau on fais un appel du genre tab[ indice ]. Si on a besoin de parcourir plusiers positions dans le tableau à la fois on peut utiliser plusieurs indices. Appelons les indice1, indice2, indice3 et ainsi de suite.

Finalement, si je veut comparer des valeurs extraites d'un tableau, je peut procéder de cette manière.

Indice1 = 1
Indice2 = 2

SI tab[ indice1 ] < tab[ indice2 ] ALORS (je fais quelque chose)

Finalement, si je veut entourer toutes les instructions dans un bloc "réutilisable" je peut procéder ainsi ou selon les conventions demandées en pseudocode :

Fonction Tri
Valeur d'entrées: Entier Tab[10]
(je fais mon tri ici)
Valeur de sortie: Entier Tab[10]*
Fin Fonction

*Une fonction a une seule valeur de sortie.

Voila. Maintenant on a tout les outils nécessaires pour attaquer le problème du tri.

Notez que le problème peut être vu autrement. Si les valeurs se trouvent dans un ordre croissant dans le tableau, cela veut aussi dire que pour une position dans le tableau, il se trouve une valeur inférieure dans la position précédente et une valeur supérieure dans la position suivante. On peut aussi remarquer que la plus petite valeur se trouve en position 1* et que la plus grande valeur se trouve en position 10.

* En programmation la première position dans un tableau c'est 0.

**droggo** · 02/01/2009, 01h09

Hai,

Envoyé par Jimalexp

* En programmation la première position dans un tableau c'est 0.

Ça dépend du langage.

En Pascal, par exemple, on peut définir les indices de début et fin d'un tableau avec les valeurs qu'on veut, tant que début < = fin, début et fin pouvant même être négatifs, ce qui est rarement utilisé, mais debut = 1 est très fréquent.

**goldy91** · 03/01/2009, 12h00

Bon voila ce que j'ai trouvé

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
 
Fonction tri (tabentier[10]:tableau d'entier):entier
Var
    i,j,min,valeur:entier
début
       Pour i de 0 a 9 faire
              min<--i
                Pour j de i+1 a 9 faire
                       Si tabentier[j]<tabentier[min] Alors
                            min<--j
                       Fin Si
                Fin Pour
       Fin Pour
       valeur<--tabentier[min]
       tabentier[min]<--tabentier[i]
       tabentier[i]<--valeur
        Retourner tabentier[i]
Fin

Voila !!

**pseudocode** · 03/01/2009, 12h57

C'est pas mal pour un début...

remarque 1 : L'échange de valeurs tabentier[min] avec tabentier[i] a lieu en dehors de la boucle "i". Donc ça parait très curieux.

remarque 2 : pourquoi retourner la valeur de "tabentier[i]" à la fin du tri ?

**Jimalexp** · 03/01/2009, 14h19

Y a de l'idée. Il reste juste à replacer ou modifier les morceaux que pseudocode a mentionné.

**goldy91** · 03/01/2009, 15h01

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
Fonction tri (tabentier[10]:tableau d'entier):entier
Var
    i,j,min,valeur:entier
début
       Pour i de 0 a 9 faire
              min<--i
                Pour j de i+1 a 9 faire
                       Si tabentier[j]<tabentier[min] Alors
                            min<--j
                            valeur<--tabentier[min]
                            tabentier[min]<--tabentier[i]
                            tabentier[i]<--valeur
                       Fin Si
                Fin Pour
       Fin Pour
       Retourner tabentier[i]
Fin

Donc c'est ça la réponse ??
Je retourne tabentier[i] car je retourne le tableau avec les valeur dans l'ordre croissant.

**Jimalexp** · 04/01/2009, 04h28

On va tester ca avec la suite de chiffres au dessus :

102, 30, -1, 5, 73, 52, 12, 10000, -10, 8

Valeurs: i = 0, min = 0, j = 1, tabentier[ j ] = 30, tabentier[min] = 102
Traitements:

Test: tabentier[j]<tabentier[min], donc tabentier[1]<tabentier[0] est vrai (donc on peut continuer)

1) min<--j, donc min = 1
2) valeur<--tabentier[min], donc valeur = 30
3) tabentier[min]<--tabentier[i], donc tabentier[1] = 102
4) tabentier[i]<--valeur, donc tabentier[0] = 30

30, 102, -1, 5, 73, 52, 12, 10000, -10, 8

( Prochain j )
Valeurs: i = 0, min = 1, j = 2, tabentier[ j ] = -1, tabentier[min] = 102
Traitements:

Test: tabentier[j]<tabentier[min], donc tabentier[1]<tabentier[0] est vrai

1) min<--j, donc min = 2
2) valeur<--tabentier[min], donc valeur = -1
3) tabentier[min]<--tabentier[i], donc tabentier[2] = 30
4) tabentier[i]<--valeur, donc tabentier[0] = -1

-1, 102, 30, 5, 73, 52, 12, 10000, -10, 8

C'est là qu'on commence à voir comment l'algorithme procède (pour faire ca plus rapidement on peut tout simplement déssiner le tableau et y placer des flêches). La valeur en position 0 seras bien le minimum. Les position des autres valeurs sont tout simplement le résultat de permutations.

Lorsqu'on arriveras au prochain i, la valeur minimale seras envoyée en position i et ainsi de suite. L'action d'avancer le i est en quelque sorte une manière de dire qu'on va s'attaquer au reste des valeurs et que le travail est fait en ce qui concerne le i précédant. Le j commence toujours en i+1 et va jusqu'à chercher la dernière position donc le reste du tableau est bien pris en compte.

Il reste donc à réflêchir à ce qui va se passer lorsque i va tendre vers la dernière position. C'est là que je pense qu'il pourrais y avoir un petit soucis. La boucle Pour se lance que si la condition est satisfaite et logiquement cela ne devrais pas poser un inconvénient en soit. Mais selon la manière dont a été conçu un langage, une erreur pourrais apparaître.

Dans l'ensemble, l'idée du pseudocode c'est de pouvoir écrire un programme sur papier sans utiliser un langage. C'est une fois qu'on a bien réflêchit à un problème qu'on peut se soucier des particularités propres au langage qu'on souhaite utiliser.

Je retourne tabentier[i] car je retourne le tableau avec les valeur dans l'ordre croissant.

Il est aussi possible de retourner un tableau dans son entierté. Pour cela il suffit de retourner le nom du tableau sans les crochets et l'indice :

Retourner tabentier

Je sais que ca peut pas paraître bizarre mais, une fois que tu auras écrit des programmes, ca prendras tout son sens.

**goldy91** · 04/01/2009, 13h21

donc tu me conseille de mettre un Sinon ??

**Jimalexp** · 04/01/2009, 14h56

C'est juste une préférence mais je mettrais l'initialisation de j en dehors de la boucle.

**goldy91** · 04/01/2009, 17h21

c'est a dire ??
peut m'écrire la partie que tu changerais stp !!

**Jimalexp** · 04/01/2009, 19h26

Ben je mettrais tout simplement j<-i+1 avant le début de la boucle. Ainsi, lorsque i est égal à 9, j ne seras pas initialisé à 10 au moment même où la boucle est lancée. C'est un détail et je testerais ca sans doute en java pour voir si une erreur se déclenche.