tri a bulle sans les doublons

Version imprimable

[resolu] tri a bulle sans les doublons

Bonjour,
Je fais tourner un tri à bulle, et je m'apercois que j'ai des
doublons que je veux virer.

l'aglo normal c'est

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
ok =  0
faire
{
pour tous les Elements
     {
      si Element n>Element n+1
        {
          ok = 1
          swap (Element n,Element n+1)
         }
       n=n+1
}
tant que pas ok

pour enlever les doublons j'ai fais ca

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
ok =  0
faire
{
pour tous les Elements
     {
      si Element n>Element n+1
        {
          ok = 1
          swap (Element n,Element n+1)
         }
 
     si Element n=Element n+1
        {
 
          Element n+1=valeur maxi
         }
 
       n=n+1
}
tant que pas ok

je souhaiterais savoir si il y a pas mieux

merci d'avance

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
Tri_A_Bulles_Optimise(Nb_Element , Tableau)
{
 
   Debut = 1
   Fin = Nb_Element - 1
   Termine = faux
 
   TAnt que (Not Termine) And (Debut < Fin)
      Termine = vrai
      pour I = Debut à Fin faire
         Si (Tableau(I) > Tableau(I + 1) ) Alors
            swap(tableau(I),tableau(I+1))
            Termine = faux
            Tampon_Fin = I
         fin si
      fin pour
      Fin = Tampon_Fin
      si(Not Termine) faire
         pour I = Fin downto Debut + 1 
            si(Tableau(I) < Tableau(I - 1)) faire
               swap(tableau(I),tableau(I+1))
               Termine = faux
               Tampon_Fin = I
            fin si
         fin pour
      fin si
   fin tant que
}

10/03/2003, 16h13
comme de bien entendu

Salut goethe,

j'ai cherché dans ton algorithme mais je ne vois pas
ce que tu fais des doublons ?

Mais dis moi si je me trompe :roll:
10/03/2003, 16h20
goethe

je t'ai donné un algo de tri a bulle optimisé : un algo de trie a bulle ne gère pas les doublons.

Si tu veux les enlever tu peux tjrs faire un parcours simple de ton tableau et les enlever au fur et a mesure : ce n'est jamais qu'une complexité en
o(n) négligeable devant les o(n²) du trie a bulle.
10/03/2003, 16h29
Invité

Note que c'est une méthode classique pour enlever les doublons. On trie puis ou parcours la liste triée.
PS: Goethe mets des O plutôt que des o dans les complexités. Pour ceux qui ne connaissent pas ça peut prêter à confusion...