Discussion :

[smalto]

ce ci est le programme je comprends tout sijplement j`ai des problemes avec la fonction bubble sortt elle meme

je ne comprends pas ces lignes suivantes la, et leur importances, si quelqu`un peut me les expliquer en details...

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
 
void bubblesort(void)
{
	int j, temp, ///////stop=0;/////////
 
	while /////////(!stop)///////////////
	{
		/////////stop = 1;////////
   		for (j=0; j<SIZE-1; j++)
      		if (ary[j] > ary[j+1])
			{
         		temp = ary[j];
				ary[j] = ary[j+1];
				ary[j+1] = temp;
				/////////stop = 0;///////////
			}
	}
}

je ne comprends pas les instruction ou j`ai inserer le ////////

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
/* Bubble Sort Example*/
 
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 100
 
int ary[SIZE];
 
void main(void);
void outputarray(void);
void bubblesort(void);
 
void outputarray(void)
{
	int i;
 
	for (i=0; i<=SIZE-1; i++)
	{
		if (i % 10 == 0) printf("\n");
   		printf("%3d ", ary[i]);
	}
	printf("\n");
}
 
void bubblesort(void)
{
	int j, temp, stop=0;
 
	while (!stop)
	{
		stop = 1;
   		for (j=0; j<SIZE-1; j++)
      		if (ary[j] > ary[j+1])
			{
         		temp = ary[j];
				ary[j] = ary[j+1];
				ary[j+1] = temp;
				stop = 0;
			}
	}
}
 
void main(void)
{
	int i;
	char ans='Y';
 
	// randomize(); // for Borland C++
	srand( (unsigned)time( NULL ) ); // for Visual C++
 
	while (ans =='Y')
	{
		for (i=1; i<=SIZE; i++)
   		ary[i-1] = rand() / 100;
 
		outputarray();
		bubblesort();
		outputarray();
 
		printf("Continue (Y/N)? ");
		scanf(" %c", &ans);
	}
}

[/quote]

[Juliunus]

Le bubblesort peut avoir à s'y prendre en plusieurs fois avant d'arriver au résultat qu'il faut.
Par exemple, si tu as la liste suivante :
3 2 1
au premier tour, l'algorithme va inverser 3 et 2 (résultat:2 3 1) puis 3 et 1 (résultat : 2 1 3)
Et là tu vois qu'il y a besoin d'une seconde passe, pour inverser 1 et 2.

Tout ça pour te dire que si dans un "tour" de l'algorithme des modifications sont appliquées, il faut refaire une passe pour être sûr que la liste est bien dans le bon ordre. Et si tu fais une passe complète sans échanger des données, c'est que la liste est triée.

Et c'est à ça que sert ta variable stop : elle se met à faux dès que lors d'une passe de l'algorithme, on a eu besoin d'échanger des valeurs.

[Matthieu Brucher]

Je te conseille de tester le programme à la main.
C'est ce que ton prof t'a sûrement conseillé, ou alors tes encadrants de TPs ou TDs. En tout cas, c'est ce que je dirai à l'un de mes élèves.
Tu prends un array comme tu veux et tu essaies.
En revanche, le code

[superspag]

Le fameux algo de tri à bulle ça me rappel des souvenir

C'est en O(N²) non ?

[smalto]

ce que je n`arrive toujurs pas a comprendre, c`est la condition du while loupe.

Code :

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

while (!stop)

stop etait au paravant initialiser a o. pouver vous me donner une autre facon d`ecrire ce while la. j`essai de comprendre tant que stop n`est pa zero c`est ce que cela veut dire je crois, mon probleme est que stop est deja egal a zero au depart donc a mon avis on ne devais meme pas entrer dnas la fonction while.....essayer de m`explique cela, car je sais que

Code :

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

!

signifie n`est pas.
merci de votre aide ...
SMALTO

[superspag]

Code :

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

1
2
 
while( ! stop )

ça veux dire tant que "stop" vaut "zero" alors je fait...
Au départ "stop" vaut "zero" donc tu execute ce qu'il y a dans la boucle.

Dans cet algo. Tu commence par mettre "stop" à "un". Puis dans la boucle "for" tu as "stop" qui repasse à "zero" S'IL Y A DU CHANGEMENT sinon il reste à "un" et la boucle "while" s'arrete...

C'est tout ce qu'il y a a comprendre. L'algo n'est pas bien compliqué :
Il fait avancer les petit chiffre en debut de tableau à chaque passe. De cette maniere il faut evidament plusieur passe... Comment on sait alors que c'est fini ? QUAND IL N'Y A PLUS DE CHANGEMENT talaaaaaa

Voilà, donc cet algo fonctionne mais ce qu'il faut retenir c'est que c'est un trés mauvais algo à éviter puisqu'il s'execute en O(N²). Les bon algo de tri s'execute plutot en O(N log N) ...

[Juliunus]

Cet algo est vraiment très lent car à chaque fois que l'on fait une modification il faut refaire le tour de TOUTE la liste.
Le cas le pire est en complexité N², et se retrouve lorsque tu as une liste triée en ordre inverse ( 5 4 3 2 1 par exemple)
voilà les résultats au bout de chaque passe :
4 3 2 1 5
3 2 1 4 5
2 1 3 4 5
1 2 3 4 5
plus une passe qui ne changera rien

Avec 5 éléments tu as donc du faire 5 passes. On retouve bien que pour N éléments, tu doive faire N passes sur ces N éléments (d'où complexité N*N). Dans un cas un peu moins pathologique, l'algorithme est bien évidemment plus rapide. Mais d'autres algorithmes (comme quicksort) peuvent être beaucoup plus rapide.

[smalto]

juste une question on peut donc ecrire

Code :

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

while(!stop)[/quote]

equivaut a

Code :

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

while(stop==0)

et je crois par ton explication que le signe \\ ! // devant stop nous dis que tant que n`est pas sont oppose continuer ou n`est pas different de zero on execute la fonction.......
j`attends confirmation de ma comprehension.......effectivement comme vous l`avez dit ce algo est inefficient, mais je voulais juste le comprendre car il fait parti de ce que j`etudie, du moins inefficient au plus inefficient..

[Luther13]

instruction while:

Code :

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

1
2
3
4
5
6
while(condition)
{
// les instruction ici s'executent tant que condition vaut 1.
// dans ton cas, on: !stop ==1  implique !(!stop) == !(1) 
// soit: stop == !(1) c'est à dire stop ==0.
}

[superspag]

operateur "!" est un operateur sur les booleens.
les instructions "while", "if", etc... prennent un booleens en parametres.
un booleen peut normalement prendre uniquement 2 valeurs : true / false
En C/C++, la valeur entiere "zero" est equivalent à la valeur booleenne "false". Toutes les autres valeurs sont "true".

[Matthieu Brucher]

Tu as trouvé ce code où ?