Bonjour

J'ai fait l'exercice du tri d'un tableau voici la fonction que j'ai écris :

void ordonnerTableau(int tableau[], int tailleTableau)
{
    int i,j, ech;
    for (j=0;j<(tailleTableau-1);j++)
    {
        for (i=0;i<(tailleTableau-1);i++)
            {
                if (tableau[i+1]<tableau[i])
                    {
                        ech=tableau[i];
                        tableau[i]=tableau[i+1];
                        tableau[i+1]=ech;
                    }
            }
    }
printf("les element du tableau ordonne sont  ");
afficherTableau(tableau,tailleTableau);
}

Mais après avoir lu sur wikipedia, je pense que ce type de tri que j'ai fait s'appelle le tri à bulles sauf que moi j'ai crée une boucle imbriquée statique qui fait des opérations non necessaires.

J'ai aussi remarqué pour le premier algorithme sur la page wikipedia qu'il est peut-être erroné, problème d'indices, voilà j'ai exécuté les itérations de cet algorithme.

// version non optimisée "Tri à Bulles"
procédure tri_bulle(tableau t)
    n = longueur(t)
    pour i allant de n-1 à 1 pas -1 faire
         pour j allant de 0 à i pas 1 faire
             si (t[j] > t[j+1]) alors
                  tmp = t[j]
                  t[j] = t[j+1]
                  t[j+1] = tmp // On échange les éléments de rang j et j+1
             fin si
         fin pour
    fin pour
fin procédure

Donc si j'execute la première itération, vous allez voir que la condition si va tester la valeur T[n] ce qui est erroné, puisque les indices du tableau commence à partir de 0.

Exemple:

Tab={12,9,6,2} n=4

Pour i=n-1=3

    j allant de 0 à i
    j=0
    T(0)<-->T(1)

    j=1
    T(1)<-->T(2)

    j=3
    T(3)<-->T(4)

    j=4
    T(4)<-->T(5)

Voilà on arive à T[5] et on dépasse le tableau. Je pense qu'ils auraient dû écrire Pour i allant de n-2 à 0. Voilà si je refait l'execution avec cette correction ((n-2) à 0) cela donne de bon résultat, le code suivant est l'execution manuelle:

Tab={12,9,6,2} n=4

Pour i= n-2 = 2

	j allant de 0 à i
	j=0
	T(0)<-->T(1)

	j=1
	T(1)<-->T(2)

	j=3
	T(3)<-->T(4)

	Tab={9,6,2,12}

Pour i=n-3= 1

	j=0
	T(0)<-->T(1)

	j=1
	T(1)<-->T(2)

	Tab={6,2,9,12}

Pour i=n-4= 0

	j=0
	T(0)<-->T(1)

	Tab={2,6,9,12}

Est-ce que j'ai raison ? sinon je veux avoir un conseil comment vous faites pour vérifier l'exactitude d'un algo sans se casser la tête de cette façon vraiment ça m'a torturé de faire tout ça

-
Edité par rogengap 21 janvier 2016 à 15:05:15

Bonjour,

A mon avis, vous confondez "algorithme" et "pseudo-code".

Je peux donner mon avis sur une code C ou sur un algorithme (en français), mais pas sur un pseudo-code.

voici le mien

#include <stdio.h>
#include <stdlib.h>

int ordonnerTableau(int tableau[], int taille);

int main(int argc, char *argv[]) {
	
	int taille,i;
	int tableau[taille];
	
	printf("entrez la taille");
	scanf("%d",&taille);
	
	for(i=0;i<taille;i++){
		printf("entrez une valeur");
		scanf("%d",&tableau[i]);
	}
	
	ordonnerTableau(tableau,taille);
	
	
	return 0;
}

int ordonnerTableau(int tableau[], int taille){
	int i,j,k;
	for(i=0;i<taille;i++){
		tableau[i];
		for(j=0;j<taille;j++){
			if(tableau[i]<tableau[j]){
				k=tableau[i];
				tableau[i]=tableau[j];
				tableau[j]=k;
			}
		}
	}
	for(i=0;i<taille;i++){
		printf("%d",tableau[i]);
	}
}

SeulSolitaire a écrit:

voici le mien

#include <stdio.h>
#include <stdlib.h>

int ordonnerTableau(int tableau[], int taille);

int main(int argc, char *argv[]) {
	
	int taille,i;
	int tableau[taille];
	
	printf("entrez la taille");
	scanf("%d",&taille);
	
	for(i=0;i<taille;i++){
		printf("entrez une valeur");
		scanf("%d",&tableau[i]);
	}
	
	ordonnerTableau(tableau,taille);
	
	
	return 0;
}

int ordonnerTableau(int tableau[], int taille){
	int i,j,k;
	for(i=0;i<taille;i++){
		tableau[i];
		for(j=0;j<taille;j++){
			if(tableau[i]<tableau[j]){
				k=tableau[i];
				tableau[i]=tableau[j];
				tableau[j]=k;
			}
		}
	}
	for(i=0;i<taille;i++){
		printf("%d",tableau[i]);
	}
}

Excuse moi mais... Quel rapport ça a avec le sujet ? Limite on s'en fout un peu de ton code là .

Seul solitaire tu as un problème dans ta fonction mais c'est vrai tu n'a pas répondu à ce que je m'attendais càd vérifier le pseudo code de wikipedia.

Coucou,

@SeulSolitaire: ligne 28 inutile et faire un affichage dans une fonction de tri est une hérésie, ça seule présence empêche cette fonction de tri d’être utilisé dans un projet pas en console (graphique, embarqué, …), la fonction de tri est déclarée comme renvoyant un int ce qui n’est pas le cas. Et le meilleur pour la fin, taille n’est pas initialisé au moment ou tu crées le tableau, le tableau à donc une taille aléatoire, affecté taille avec une valeur après sa création n’a aucun impact sur le tableau, ce qui entraîne des risques d’accès invalides et donc le fonctionnement de ton programme tient du miracle mais en plus, intégré ce code à un autre projet peut entraîner des bogues immondes (des changement de variables incompréhensibles p.ex.). Bref code à corriger, et dans l’état actuel, à fuir.

@rogengap: Je suis d’accord avec ce que tu dis avant ton exemple (et je n’ai pas lu ton exemple), AMHA il faudrait corriger la seconde boucle "pour" par "pour j allant de 0 à i-1 pas 1 faire".

fscorpio a écrit:

Coucou,

@SeulSolitaire: ligne 28 inutile et faire un affichage dans une fonction de tri est une hérésie, ça seule présence empêche cette fonction de tri d’être utilisé dans un projet pas en console (graphique, embarqué, …), la fonction de tri est déclarée comme renvoyant un int ce qui n’est pas le cas. Et le meilleur pour la fin, taille n’est pas initialisé au moment ou tu crées le tableau, le tableau à donc une taille aléatoire, affecté taille avec une valeur après sa création n’a aucun impact sur le tableau, ce qui entraîne des risques d’accès invalides et donc le fonctionnement de ton programme tient du miracle mais en plus, intégré ce code à un autre projet peut entraîner des bogues immondes (des changement de variables incompréhensibles p.ex.). Bref code à corriger, et dans l’état actuel, à fuir.

A propos du code de seulsolitaire si on profitait pour analyser plutôt sa fonction ordonnerTableau, tout d'abord pour la première itération si tableau[0] contient la valeur la plus petite, cette valeur va être décalée jusqu'à la fin de tableau donc on fait l'inverse de ce qu'on voulait cad classer dans l'ordre croissant, après ça je ne sais pas comment analyser les autres itérations je perd le fil donc c'est aussi une occasion pour que quelqu'un m'aide à analyser comment des boucles vont affecter le resultat final.

Analyser un code est très difficile.
Je vais détailler les étapes à peu près en même temps que je les faits.
Il faut arriver à découper le code en morceaux, à les comprendre séparément puis à reconstituer le tout.

Pour commencer :

k = tableau[i];
tableau[i] = tableau[j];
tableau[j] = k;

Ceci échange le contenu des cases i et j.

Intéressons nous à la deuxième boucle :

for(j = 0; j < taille; j++)
{
    if(tableau[i] < tableau[j])
    {
        // Échanger les cases i et j
    }
}

Pour une case i donnée, ce bout de code parcourt tout le tableau (for) et pour chaque case il regarde si elle est plus grande que la case i (if) si oui elles sont échangées. En d’autre terme, ce bout de code place la plus grande valeurs dans la case i ET modifie toutes les valeurs d’une manière difficilement compréhensible. En effet pour toute case supérieure à la case i, un échange est effectué. Si je pars du tableau 1, 3, 5, 2, 7 pour i = 0 ça donne le déroulement :

1 3 5 2 7
-> j = 0
1 3 5 2 7
-> j = 1
3 1 5 2 7
-> j = 2
5 1 3 2 7
-> j = 3
5 1 3 2 7
-> j = 4
7 1 3 2 5

On peut voir que le 7 à été placé au début et que les autres cases ont changé pendant le déroulement de la procédure mais aussi à la fin.
On commence avec 1, 3, 5, 2, 7 pour finir avec 7, 1, 3, 2, 5, l’ordre des cases autre que le maximum passe de 1, 3, 5, 2 à 1, 3, 2, 5. Ce code ne fait pas que placer le maximum à la case i.

Reste à voir comment ce comporte ce bout code quand on l’utilise sur toutes les cases du tableau une à une (penser à utiliser une feuille et un crayon).
Au premier coup i = 0, le maximum est placé au début, l’ordre du reste du tableau est changé, aucune importance le tableau n’était de toute façon pas trié, mélanger un peu plus ou un peu moins n’a pas d’importance.

On sait maintenant que la case 0 est la plus grande. (et c’est d’ailleurs la seule chose qu’on sait)

Au second coup i = 1, c’est de suite plus intéressant, la case 0 est forcément échanger avec la case 1, car c’est la plus grande et c’est la première opération effectuée (j = 0). On sait maintenant que la case 1 est la plus grande et que la case 0 contient maintenant une valeur inférieur ou égale à la 1, les cases 0 et 1 sont dans le bon ordre. Le reste du tableau n’aura aucun impact, car on a déjà la valeur la plus grande.

On a déjà établit que la deuxième boucle place le plus grand sur la case i et modifie de manière difficilement compréhensible le reste, cependant avant le troisième coup (i = 2) on voit que le tableau prend une forme intéressante, les éléments avant la case i sont trié (la case 0 et 1).
On a : a, b, c, … avec a, b dans le bon ordre et c la case i. La seconde boucle dont le boulot et de mettre la plus grande valeur dans la case i et ce pour chaque case rencontre un cas particulier, elle va en effet rencontrer les cases dans l’ordre croissant, pour toutes cases avant i.

Je m’arrête dans le déroulement ici, car le résultat est intéressant, en effet on peut généraliser cette situation de la manière suivante, toutes les cases avant i sont en ordre croissant, la case i est inconnu mais inférieur à la case i - 1 qui est la plus grande, les suivantes sont toutes inférieures à la case i - 1 et dans un ordre quelconque et peuvent être inférieures, égales ou supérieures à la case i. Si l’on trouve un fonctionnement intéressant pour un nombre quelconque de valeurs avant i, ce sera très utile pour la suite.

Le tableau a donc cette forme : a, b, c, d, e, f, i, ?, ?, ?, …

Les valeurs a, b, c, d, e, f sont croissantes et la case f est supérieure ou égale aux autres (c’est l’hypothèse de départ), la case i est forcément inférieure ou égale à la case f.

Les cases a, b, c, d, e, f peuvent être divisé en deux groupes, celles qui sont inférieures ou égales à i et celles qui ne le sont pas, vu qu’elles sont dans l’ordre croissant, les deux groupes sont clairement séparés.

Les premiers éléments parcouru par la boucle sont ceux qui sont inférieurs, vu qu’ils sont inférieurs la boucle ne fait rien, le groupe des éléments inférieurs ou égaux reste trié, vient ensuite le groupe des éléments supérieurs, comme ils sont dans l’ordre croissant, les suivants sont forcément supérieur (ou égaux) aux précédents, par conséquent toutes les cases seront échangé une à une avec i, ce qui revient à placer la case i devant ce groupe. Le premier échange place la case i en première place (du groupe), le second place la case qui été en première place en seconde place, le troisième place la case qui été en seconde place en troisième place, etc. (si deux cases sont identiques, les échanger ou pas ne change rien).

On a donc : les valeurs inférieures à i, i, les valeurs supérieures à i, le reste du tableau.

Dans la case i se trouve maintenant la valeur la plus grande, le reste de la boucle ne fera donc rien.
Le résultat est intéressant car maintenant toutes les cases jusqu’à i sont triées.
On a : a, b, c, d, i, e, f, ?, ?, ? avec i à la bonne place.

Je revient là ou j’ai laissé le déroulement de l’algo de tri, on a : a, b, c, … avec a, b dans le bon ordre et c la case i.
On sait maintenant que dans ce cas la case i va être ajouté au bon endroit, à la fin de ce tour de boucle on aura donc a, b, c dans le bon ordre et ainsi de suite.

Le tableau évolue de la façon suivante :

?, ?, ?, ?
d, ?, ?, ?
b, d, ?, ?
b, c, d, ?
a, b, c, d

(l’ordre d’ajout de a, b et c est inconnu)

C’est un tri par insertion. (et il sera sûrement beaucoup plus simple de comprendre mon pavé après avoir appris ce qu’est un tri par insertion…)

Salut fscorpio, je te remercie pour cette longue explication surtout je pense que tu a fait trop d'effort pour rendre ça facile à comprendre de cette façon, je n'ai rien à dire de plus vu les détails que tu as apporté j'ai bien compris ce raisonnement et je reconnais que c'est un peu difficile à assimiler.

Tu m'a surpris juste au moment ou tu m'a dit que c'est un tri par insertion parce que avant que je poste mon sujet j'ai déjà lu l'article sur le tri par insertion sur wikipedia et dans l'algorithme présenté sur cet article je pense que le concepte d'insertion apparait plus clairement vu qu'on fait un décalage des élements du tableau et on place le bon élement au bon endroit.

Voici l'algo dont je parle :

 procédure tri_insertion(tableau T, entier n)
      pour i de 1 à n-1
          x ← T[i]
          j ← i
          tant que j > 0 et T[j - 1] > x
              T[j] ← T[j - 1]
              j ← j - 1
          fin tant que
          T[j] ← x
     fin pour
  fin procédure 

J'ai vraiment envi de l'analyser comme tu l'a fait avec le code de seulsolitaire mais je ne possède pas une méthodologie pour decrire progressivement le déroulement de l'algorithme, j'ai besoin d'autres exemple d'analyse à l'instar de la tienne pour avoir de l'expérience avec ça.

Je vais revenir pour reconvertir ce dernier code en langace C, et peut-être le comparer avec le code de seulsolitaire pour voir qui est celui qui utilise un nombre d'opération plus petit, c'est à dire lequel est plus rapide et performent pour de gros tableaux à trier.

Merci infiniment

-
Edité par rogengap 22 janvier 2016 à 0:57:58

rogengap a écrit:

Donc si j'execute la première itération, vous allez voir que la condition si va tester la valeur T[n] ce qui est erroné, puisque les indices du tableau commence à partir de 0.

Dans le pseudo-code de Wikipédia, les indices du tableau vont de 1 à n.

Marc Mongenet a écrit:

Dans le pseudo-code de Wikipédia, les indices du tableau vont de 1 à n.

Non il vont de 0 à n-1 puisque la boucle du compteur j démarre à partir de 0 (pour j allant de 0 à i)

rogengap a écrit:

Marc Mongenet a écrit:

Dans le pseudo-code de Wikipédia, les indices du tableau vont de 1 à n.

Non il vont de 0 à n-1 puisque la boucle du compteur j démarre à partir de 0 (pour j allant de 0 à i)

Juste. Le problème, c'est que n'importe qui change continuellement ce pseudo-code :

https://fr.wikipedia.org/w/index.php?title=Tri_%C3%A0_bulles&diff=121868243&oldid=115812431

https://fr.wikipedia.org/w/index.php?title=Tri_%C3%A0_bulles&diff=115812431&oldid=113743018

https://fr.wikipedia.org/w/index.php?title=Tri_%C3%A0_bulles&diff=113734155&oldid=112453220

https://fr.wikipedia.org/w/index.php?title=Tri_%C3%A0_bulles&diff=111170406&oldid=110024616

etc.

Il faut que je trouve un pseudo-code de référence, et que je le mette dans l'article.