Aller au menu - Aller au contenu

Le tri à bulles

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page 1 
Pseudo Commentaire
Page 1 
Hors ligne Dutiona # Posté le 26/09/2008 à 12:18:59
Vis pour être heureux !
Avatar

Ville : Toulouse
Pays : France métropolitaine
Études : EISTI

 Salut,

Tu expliques bien mais il y a une implémentation bien plus simple pour ce tri :
Code : C
1
2
3
4
5
6
7
8
for(int i = 0 ; i < taille-1 ; i++){
  if(tab[i] > tab[i+1]){
    temp = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = temp;
    i = 0;
  }
}


Je pense que tu devrais préciser que le tri à bulle est un tri qui se prête bien au multithreading. Plusieurs bulles peuvent être envoyées en même temps (dans ce cas, mon implémentation ne tiens plus, évidement). Parle aussi du tri shacker (les bulles circulents dans un sens puis dans l'autre).

Très bon tuto, j'aime beaucoup ton explication sur la complexité ;) .

17.


Bisous, Nyu
#LGDF: winzou vaincra !
Défiez ma brute !
Eclipse user | Ubuntu (KDE) user | php/sql/xhtml/css/xml/xsl/javascript/java/python/perl/c/scheme/ada/uml/ocl coder.
Framework in use : Seraframework (my own one).
In Microeisti staff.
 
Hors ligne shareman # Posté le 26/09/2008 à 16:52:59
Faisons semblant
Avatar

 Salut,

Merci à toi, en effet, je n'avais jamais vu cette implémentation, j'ai refais en gros celle que l'on trouve un peu partout sur le net. Je vais voir ça plus en détail.

shareman
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne SpaceFox # Posté le 27/09/2008 à 07:13:37
Utilise ton cerveau !
Avatar
Validateurs
Flux RSS
close

Études : UTT

 J'avoue ne pas bien comprendre l'intérêt d'un tuto sur un système de tri inutile dans 99% des cas (il paraît que ça peut servir, personnellement j'ai jamais trouvé où mais bon...).
Cela dit, le tuto en lui-même est bien fait.
Image utilisateur
 
Hors ligne Nanocom # Posté le 27/09/2008 à 07:55:40
Avatar

Ville : Ittenheim
Pays : France métropolitaine
Études : INSA Lyon

 Dans l'introduction : la plus part => la plupart
Hors ligne Nanoc # Posté le 29/09/2008 à 14:46:33
Aimez-vous le C++ ?
Avatar
Validateurs

Ville : Durham
Pays : Royaume-Uni
Études : EPFL

 Je plussoie la remarque de SpaceFox.

Le code proposé par Dutonia ne fonctionne pas. Le premier élément n'est pas trié.

Quel est l'intérêt de la version récursive ? Y en a-t'il un ?

Qu'est-ce que tu entends par "opération" quand tu dis que l'algorithme fait n(n-1)/4 opérations ?

C'est quoi son "originalité". Je vois pas ce qu'il y a d'original dans une méthode tellement intuitive que quasiment tous les débutants la codent une fois dans leur vie.

Quel intérêt d'utiliser un tri-bulle sur une petite liste ?

A part l'utilisation des booléens, j'aurais plutôt dit que ton code est en C. D'ailleurs, la taille devrait être un "unsigned int" ou mieux, un "size_t".
Auteur d'un livre : Programmez avec le langage C++
Mes tutos : [C++] Cours officiel pour débutants, [C++] Manipulateurs de flux, [C++] Pointeurs sur fonctions, [C++] Maîtriser le compilateur g++, [C++] Déboguer avec Code::Blocks

 
Hors ligne Dutiona # Posté le 29/09/2008 à 16:24:11
Vis pour être heureux !
Avatar

Ville : Toulouse
Pays : France métropolitaine
Études : EISTI

 Au temps pour moi, c'est pas i = 0 mais i = -1. Mais sinon, dans la logique, mon code fonctionne parfaitement et est évidement beaucoup plus simple que les codes proposés dans ce tuto.
J'ai donc :
Code : C
1
2
3
4
5
6
7
8
for(int i = 0 ; i < taille-1 ; i++){
  if(tab[i] > tab[i+1]){
    temp = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = temp;
    i = -1;
  }
}


Et si tu veux tester, voici le prog qui va avec :
Code : C
 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
/*! 
	\file    tribulle.c
	\author  Dutiona
	\version 0.1
	\brief   Teste une implémentation simple du tri à bulle
	\remarks aucune
*/
#include <stdio.h>
#include <stdlib.h>

/*! 
 *  \fn      int main(int argc, char** argv)
 *  \author  Dutiona
 *  \version 0.1
 *  \brief   Fonction principale du programme
 *  \param   argv : Tableau des arguments
 *  \param   argc : Nomber d'arguments
 *  \return  int : signal au shell
 *  \remarks aucune
*/
int main(int argc, char** argv){
	int tab[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	int taille = 10;
	int temp;
	int i = 0;

  for(i = 0 ; i < taille-1 ; i++){
		if(tab[i] > tab[i+1]){
			temp = tab[i];
			tab[i] = tab[i+1];
			tab[i+1] = temp;
			i = -1;
		}
	}
	for(i = 0; i < taille; i++){
		printf("%d ", tab[i]);
	}
	printf("\n");

  return (0);
}


La version récursive est plus facilement adaptable pour des portages en lisp ou en scheme mais uniquement lorsque la récursivité est complette... Ici, la fonction est récursive et utilise aussi des boucle. L'intérêt est mitigé.
Un autre intérêt de l'implémentation récursive est de pouvoir adapter l'implémentation pour multithreader chaque appelle de fonction. Il ne reste plus qu'à poser les mutex au bon endroit.

Quand il dit "opération" il veut dire le nombre d'échanges d'éléments du tableau.

Quant à l'originalité, je pense que tu as pas bien comparés tous les tris. Par exemple, le tri à bulle, pour un tableau de n éléments déjà triés est plus performant (et de loin) au quicksort... Tu as O(n) avec les bulles et O(n²) avec le quicksort... Comme quoi tous les algos ont leur points fort et leur points faibles ;) .

Pour ce qui est d'utiliser le tri-bulle sur une petite liste hé bien en partant du principe que la complexité est de O(n²), on voit bien que plus il y a d'éléments moins c'est efficasse. Pour des listes (ou tableaux) avec un nombre d'éléments <= 20, ce tri reste performant par rapport aux autres algo de tri.


Pour ce qui est des unsigned int ou size_t, je pense que des détails d'implémentation de ce niveau ne sont pas très important pour un tuto d'algo.


Bisous, Nyu
#LGDF: winzou vaincra !
Défiez ma brute !
Eclipse user | Ubuntu (KDE) user | php/sql/xhtml/css/xml/xsl/javascript/java/python/perl/c/scheme/ada/uml/ocl coder.
Framework in use : Seraframework (my own one).
In Microeisti staff.
 
Hors ligne shareman # Posté le 29/09/2008 à 19:36:11
Faisons semblant
Avatar

 Sinon, pour satisfaire Nanoc, je vais éditer sous peu mon code et le renvoyer à la validation. Pourquoi ne pas parler du tri Shuttle tant que j'y suis, ce serait une bonne idée. ;)

@+
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne shareman # Posté le 08/10/2008 à 17:22:57
Faisons semblant
Avatar

 Bonjour à tous,

J'ai édité le tutoriel et voici les changements :
- Création d'une sous-partie "en savoir plus" dans laquelle j'explique le principe du tri à bulles bidirectionnel et donne quelques liens externes.
- Retouche de la sous-partie "implémentation", avec l'adaptation du code proposé à la bibliothèque standard du C++ et avec la suppression de la sous-sous-partie "implémentation récursive".

Bonne lecture ! :)
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne lamineve # Posté le 31/10/2008 à 10:30:30

salut tout le monde.
je suis un debutant
je me perds un peu dans ce tuto à propos de " table_en_ordre"
1 pourquoi l'avoir initialisé à FALSE?
2 pourquoi avoir ecrit WHILE(!table_en_ordre) d'après moi comme on l'a initialisé à False !table_en_ordre signifie qu'il vaut maintenant TRUE or ce cas est une condition de sortie de boucle.
Bref expliquez moi clairement table_en_ordre
MERCI d'avance
Hors ligne shareman # Posté le 31/10/2008 à 13:37:30
Faisons semblant
Avatar

 Salut ! :)

tab_en_ordre est un booléen qui permet de tester si au moins un échange a été réalisé lors d'un passage sur le vector. Si oui, alors tab_en_ordre vaut false et on boucle ! Sinon elle vaut true, auquel cas il n'y avait plus rien à inverser et donc on sort du while. Il faut l'initialiser à false parce que sinon, on entrera jamais dans la boucle et le vector ne sera pas trié.
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne shareman # Posté le 14/07/2009 à 14:13:43
Faisons semblant
Avatar

 Un tri à bulles simple en OCaml, pas cherché à être optimisé :

Code : OCaml
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
let tri_bulles l =
  let rec trib i m l =
    let rec walk = function
    | ([] | _::[]) as l -> l
    | f::l::q ->
      if f < l then f:: walk (l::q)
      else l:: walk (f::q)
    in if i = m then l
    else trib (i + 1) m (walk l)
  in trib 0 (length l - 1) l
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne owolaby001 # Posté le 23/07/2009 à 19:55:35

merci
Hors ligne raphamil # Posté le 24/08/2009 à 12:27:45
Avatar

Études : Université de Bordeaux

 Je trouve que tes codes pourraient être un peu plus "C++", en utilisant les itérateurs de la STL (et en plus on est indépendant du type de conteneur) :

Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
template<class Iterator>void Bulle(Iterator first, Iterator last) {
    /*
    bool trie = false;
    while(!trie) {
        Iterator it = first;
        trie = true;
        while(++it != last) {
            if(*(it - 1) > *it) {
                trie = false;
                std::swap(*(it - 1), *it);
            }
        }
    }
    */
    for(Iterator it = first; it != last; ++it) {
        if(*it > *(it + 1)) {
            std::swap(*(it + 1), *it);
            it = first - 1;
        }
    }
}


La deuxième partie provoque une boucle infinie, je ne comprends pas bien pourquoi :/

Utilisation :

Code : C++
 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iomanip>

static const size_t g_TAILLE = 8000;


int RandomNumber() {
    return rand() % g_TAILLE + 1;
}
void Randomize(std::vector<int>& i) {
    std::generate(i.begin(), i.end(), RandomNumber);
}

float Chrono(clock_t start, clock_t end) {
    return (static_cast<double>(end) - start) / CLOCKS_PER_SEC;
}

inline void TicTac() {
    static clock_t start;
    static bool tic = true;
    if(!(tic = !tic)) {
        start = clock();
    } else {
        clock_t end = clock();
        cout << std::setprecision(40) << Chrono(start, end) << 's' << std::endl;
    }
}

int main() {
    std::vector<int>tab(g_TAILLE);
    srand(time(NULL));

    Randomize(tab); TicTac();
    Bulle(tab.begin(), tab.end()); TicTac();
    //
    Randomize(tab); TicTac();
    std::sort(tab.begin(), tab.end()); TicTac();
    
    //cout << std::endl;
    return 0;
}
Les langages fonctionnels sont un rien spéciaux, mais ils changent votre manière de voir un programme. Si vous ne connaissez que des dérivés du C (PHP, Python, etc.), changez votre manière de voir ici, et avec OCaml, Haskell, ou Scheme.
 
Hors ligne shareman # Posté le 30/08/2009 à 20:51:49
Faisons semblant
Avatar

 Citation : raphamil
Je trouve que tes codes pourraient être un peu plus "C++"

Il ne faut pas perdre de vue une chose : j'ai écrit les codes de ce tutoriel pour qu'un débutant en C puisse les comprendre (parce que ce seront principalement eux qui liront ces codes et qui vont chercher à les comprendre, et il n'est pas rare de voir un débutant essayer d'implémenter un tri bulles sur le forum C) tout en restant dans mon langage de prédilection qui est le C++. Si j'avais voulu faire "plus C++" comme tu dis, j'aurais effectivement utilisé les iterator, qui permettent un puissant polymorphisme paramétrique (c'est le but).

Citation : raphamil
Code : C++
1
2
3
4
5
6
for(Iterator it = first; it != last; ++it) {
        if(*it > *(it + 1)) {
            std::swap(*(it + 1), *it);
            it = first - 1;
        }
    }


Cette implémentation n'est pas bonne pour au moins trois raisons :
- "last" pointe par définition "après la séquence", donc à la dernière itération de ta boucle for, ça va coincer au moment de faire *(it+1), donc au moment où le programme va chercher à déréférencer last ;
- Le "plus"- ainsi que le "moins" binaire ne sont pas des opérateurs supportés par tous les iterators, par exemple pas par ceux de std::list. Donc en écrivant it+1 ou first-1, tu casses une partie du polymorphisme qu'offrent les iterators ;
- Ton implémentation est en O(n^3) au pire des cas.
Image utilisateur
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
 
Hors ligne sidarape # Posté le 12/02/2010 à 19:42:26
Voici votre E.P.P.Z monsieur!
Avatar

Ville : Québec, qc
Pays : Canada
Études : Cégep Sainte-Foy

 Citation : Dutiona
Code : C++
1
2
3
4
5
6
7
8
for(int i = 0 ; i < taille-1 ; i++){
  if(tab[i] > tab[i+1]){
    temp = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = temp;
    i = -1;
  }
}

Légèrement moins performant étant donné que tu parcours tous le tableau à chaque fois au lieu de le réduire comme dans les tutoriel.
Image utilisateur

Vive le Québec Libre!!!
 
Hors ligne SylafrsOne # Posté le 30/06/2011 à 18:38:07
Ga Bu Zo Meu
Avatar

Ville : Brunoy
Pays : France métropolitaine
Études : IUT Orsay

 Pourquoi ne pas l'avoir mis ici : Algorithmes divers multi-langage plutot ? (c'est toi le PO en plus ^^').
(Ou ne pas avoir fait de pub sur ce topic, à mon avis peu visité, par les débutants ? ^^')
__________________________________

Peut-être pouvons nous "retranscrire" ce topic (pour les tris) en big-tuto ?
ça peut-être lourd, mais faisable en pas trop de temps si on s'y met à plusieurs ^^
Image utilisateur
Image utilisateur

ce n'est jamais un bug : c'est une petite erreur.
perror(const char *) could save your life
pensez aux balises de code ! (bouton </>)
Exercices pour les débutants [C]
Message sous license WTFPL
 
Hors ligne pb_ee1 # Posté le 16/03/2012 à 06:04:53
Meow =^.^=
Avatar

Études : EFREI

 L'explication de la complexité est à mon goût vraiment peu claire. Voici une explication un poil plus compréhensible que de passer par la notation de Landau.

Si on prend le pire des cas, c'est-à-dire une liste triée dans le sens inverse où on veut la trier (par exemple {18, 14, 10, 8, 6, 2, 1} que l'on veut trier en {1, 2, 6, 8, 10, 14, 18}), il est facile de calculer combien de comparaisons l'algorithme va effectuer.

Au premier passage, l'algorithme va effectuer n comparaisons (ici n valant 7) pour obtenir la liste suivante: {14, 10, 8, 6, 2, 1, 18}.

Au deuxième passage, l'algorithme va effectuer (n - 1) comparaisons seulement car on ignore le dernier élément qui, on le sait grâce au premier passage, est le plus grand. On obtient alors: {10, 8, 6, 2, 1, 14, 18}.

Et ainsi de suite jusqu'à la dernière comparaison entre 2 et 1.

Le nombre de comparaisons effectuées est donc égal à: n + (n - 1) + (n - 2) + ... + 1, soit en simplifiant n * n - (1 + 2 + ... + (n - 1)). On garde l'élément croissant le plus vite dans la formule, soit n * n, d'où la conclusion: la complexité de cet algorithme est de O(n²).
Java - xHTML/CSS - XML - PHP/MySQL - Perl - LUA
Comment ça "parse error"! Grumpf, encore les serveurs qui sont plantés :-°
 
Pour accéder à cette section
Connectez-vous !
connexion_rpx