Tri à bulles et complexité
Bonjour à tous,
Voici mon un petit code que j'ai trouvé sur le net et que j'ai modifié pour me satisfaire :
Code:
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
|
public class Tri{
public static void main(String [] args)
{
int tabk[] = {1029,8,1,4,2,190,2999,90,3,0};
int Exchange;
int compteurA=0;
int compteurB=0;
int v=0;
//Tri à bulles
//BOUCLE A
for(int a=0;a<N;a++)
{
//BOUCLE B
for(int b=0;b<N;b++)
{
//Echange des valeurs
if (tabk[a]<tabk[b])
{
Exchange=tabk[a];
tabk[a]=tabk[b];
tabk[b]=Exchange;
}
//compte le nombre d'entrée dans la boucle b
compteurB=compteurB +1;
}
//compte le nombre d'entrée dans la boucle a
compteurA=compteurA +1;
}
System.out.println("COMPTEUR A: "+compteurA);
System.out.println("COMPTEUR B: "+compteurB);
System.out.println("");
//Affiche le tableau trié
while(v<10)
{
System.out.println(tabk[v]);
System.out.println(",");
v++;
}
}
} |
Ce code fonctionne très bien et tri parfaitement mon tableau, le seul problème c'est qu'il ne ressemble pas du tout à un tri à bulles.
En effet un tri a bulles est censé comparé l'élément courant du tableau avec son successeur, soit tab[i]>tab[i+1]. Or là, on dirait qu'il compare l'élément courant avec chacun des éléments du tableau et cela à tour de rôle (La boucle B le fait).
De plus voici ce que me donne comme résultat les compteurA et compteurB :
Code:
1
2
3
|
COMPTEUR A: 10
COMPTEUR B: 100 |
Or il me semble bien que la compléxité d'un tel algo est O(n), soit n*n, mais 10 * 100 = 1000 !!! Dois-je comprendre par là que mon algo n'est pas un tri à bulles car sa complexité ne semble pas la même, ou bien, que tout simplement COMPTEUR B = 100 car 10*10 !?
Ma question est donc celle-ci, comment dois-je comprendre ce que j'ai codé ?
Je vous remercie d'avance de vos réponses et de vos éclaircissements.
