Tri à bulle optimisé

Bonjour

J'ai vu un tri à bulle sur les sources C : http://c.developpez.com/sources/?pag...THME_tri_bulle
Pour moi, ce tri n'est absolument pas optimisé ! Même pour un tri à bulle !

Je proposerais, avec chaine, la liste à trier et l sa longueur :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

for (i=0;i<l-1;i++) { j_max=i; c_max=chaine[i]; for (j=i+1;j<l;j++) { if (chaine[j]<c_max) { j_max=j; c_max=chaine[j]; } } chaine[j_max]=chaine[i]; chaine[i]=c_max; }

---

En gros, je cherche le plus petit, je le mets devant en échangeant sa place avec celui de devant et je recommence , mais en commençant une case plus loin.

Citation:

---

Envoyé par troumad

Bonjour

J'ai vu un tri à bulle sur les sources C : http://c.developpez.com/sources/?pag...THME_tri_bulle
Pour moi, ce tri n'est absolument pas optimisé ! Même pour un tri à bulle !

---

Salut

Le principe du tri à bulle est le suivant: on balaye le tableau et chaque fois qu'un élément n'est pas à sa bonne place par rapport à celui qui le suit ben on les permutes.
Et on recommence la boucle tant qu'il y a eu au-moins une permutation. Personne n'a jamais prétendu qu'un tri à bulle était optimisé...

Il existe d'ailleurs le tri à bulle dit "optimisé" où on mémorise la position de la première permutation de la boucle. Et à la boucle suivante on ne repart que de cette position. Ca améliore "un peu" les perfs mais c'est que dalle par rapport aux algos comme quicksort...

Citation:

---

Envoyé par troumad

Je proposerais, avec chaine, la liste à trier et l sa longueur :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

for (i=0;i<l-1;i++) { j_max=i; c_max=chaine[i]; for (j=i+1;j<l;j++) { if (chaine[j]<c_max) { j_max=j; c_max=chaine[j]; } } chaine[j_max]=chaine[i]; chaine[i]=c_max; }

---

En gros, je cherche le plus petit, je le mets devant en échangeant sa place avec celui de devant et je recommence , mais en commençant une case plus loin.

---

L'optimisation d'un tri se mesure selon sa complexité (le nombre d'itérations). J'ai pas regardé en détail ton code et son fonctionnement mais étant donné qu'il y a 2 boucles imbriquées où chaque boucle balaye le tableau, ça donne un ordre de grandeur, pour un tableau de N éléments, de N² itérations (attention, il s'agit ici d'un ordre de grandeur et non d'une valeur exacte). Et donc ton algo a malheureusement la même complexité que celle du tri à bulles...

Ce que tu proposes est, sauf erreur de ma part, l'algorithme proposé dans le source qui précède immédiatement celui du tri à bulle : Tri par maximum

Citation:

---

Envoyé par diogene

Ce que tu proposes est, sauf erreur de ma part, l'algorithme proposé dans le source qui précède immédiatement celui du tri à bulle : Tri par maximum

---

Il me semble aussi !
J'avais toujours cru que comme ça, je faisais du tri par bulle ! L'intérêt du tri par maximum plutôt que du tri par bulle, c'est qu'on limite le nombre d'affectation.

Citation:

---

Envoyé par troumad

J'avais toujours cru que comme ça, je faisais du tri par bulle ! L'intérêt du tri par maximum plutôt que du tri par bulle, c'est qu'on limite le nombre d'affectation.

---

Ce que tu proposes est un tri par sélection (aussi appelé tri par extraction).

Citation:

---

Envoyé par Sve@r

L'optimisation d'un tri se mesure selon sa complexité (le nombre d'itérations). J'ai pas regardé en détail ton code et son fonctionnement mais étant donné qu'il y a 2 boucles imbriquées où chaque boucle balaye le tableau, ça donne un ordre de grandeur, pour un tableau de N éléments, de N² itérations (attention, il s'agit ici d'un ordre de grandeur et non d'une valeur exacte). Et donc ton algo a malheureusement la même complexité que celle du tri à bulles...

---

C'est effectivement du O(n²) comme le tri à bulle mais il a l'avantage, comme le fait remarquer troumad, de ne nécessité que peu d'échange, ce qui peut être intéressant dans certain cas.
Par contre, sur des ensembles déjà triés ou quasiment triés, il reste en O(n²) alors que la complexité du tri à bulle chute dans ces cas particuliers.

Merci pour vos explications.