Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.

Forum Casio - Autres questions


Index du Forum » Autres questions » trie à bulle d'une liste
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

trie à bulle d'une liste

Posté le 19/04/2014 14:48

bonjour
j'ai entendu parler du trie à bulle dans le topic trier un liste mais je n'ai absolument rien compris or cela permettrait de n'utiliser que 3listes de sauvegarde pour mon niaiseux au lieu de 5 !!!
quel code rentrer pour trier la List 1 de 6 à 10 par exemple ?
merci de votre aide


1, 2 Suivante
Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 14:56 | #


L'algoritme du tri à bulle est simple.
On selectionne la premiere valeur
Pour chaque autre valeur (on descend la liste)
  Si la valeur est inferieure
    On echange les deux valeurs
    On recommence a boucler avec la nouvelle valeur (de meme rang)
Si aucune valeur n'est inferieure
  On selectionne la valeur suivant celle qui etait selectionnee
Si la valeur selectionnee est la derniere
  Le tri est termine


Dis-moi si je n'ai pas été assez clair.
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:05 | #


alors ca donnerai ca :*
Lbl 0
For 1→A To Dim (List 1)-1
If List 1[A]<List 1[A+1]
Then List 1[A]→B
List 1[A+1]→List 1[A]
B→List 1[A+1]
Goto 0
IfEnd
Next

Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:09 | #


Non, ici tu ne vérifies que l'élément suivant, alors que tu dois vérifier toute la liste.

1->A
Lbl 0
For A+1->I To Dim List 1
If List 1[I]<List 1[A]
Then List 1[I]->X
List 1[A]->List 1[I]
X->List 1[A]
Goto 0
IfEnd
Next
A+1->A
A=Dim List 1=>Goto END
Goto 0


Ça doit être ça.
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:12 | #


oui mais le mien était bon non ? n'est que du dois repartir du début de la liste mais si Dim List 1=5 ca va non ?
Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:15 | #


Oui, le tien vérifie bien toute la liste, mais il ne fait qu'échanger un élément de la liste avec le suivant.
Exemple avec la liste
5, 3, 4, 1

qui deviendra
3, 4, 1, 5
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:17 | #


bah non ya le
If List 1[A]<List 1[A+1]


Ajouté le 19/04/2014 à 15:17 :
ca va trier dans l'ordre décroissant puisque ya que si c'est inférieur que ca échange
Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:20 | #


Oui, ça c'est une erreur de ma part. ^^'
Tu n'as qu'à mettre > si tu veux ordre croissant.

Je reprends ton algorithme.
5, 3, 4, 1 -- A=1, 5>3 donc on inverse.
3, 5, 4, 1 -- A=2. 5>4 donc on inverse.
3, 4, 5, 1 -- A=3. 5>1 donc on inverse.
3, 4, 1, 5 -- A=4. L'algorithme est termine.


Tu vois où est l'erreur ?
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:28 | #


non
j'ai mis un Goto 0 pour recommencer du début
donc ca fera :
5, 3, 4, 1 -- A=1, 5>3 donc on inverse et on reprend du début.
3, 5, 4, 1 -- A=1. 3<5 on continue.
3, 5, 4, 1 -- A=2. 5>4 donc on inverse et on reprend du début.
3, 4, 5, 1 -- A=1. 3<4 on continue.
3, 4, 5, 1 -- A=2. 4<5 on continue.
3, 4, 5, 1 -- A=3. 5>1 donc on inverse et on reprend du début.
3, 4, 1, 5 -- A=1. 3<4 on continue.
3, 4, 1, 5 -- A=2. 4>1 donc on inverse et on reprend du début.
3, 1, 4, 5 -- A=1. 3>1 donc on inverse et on reprend du début.
et 1,3,4,5 et la tout va bien ca vérifie et c'est fini



Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:35 | #


Avec mon algorithme
5, 3, 4, 1
3, 5, 4, 1
1, 5, 4, 3
1, 4, 5, 3
1, 3, 5, 4
1, 3, 4, 5


Un poil plus court il me semble.
Excuse-moi, en effet ton algorithme était correct, ce qui m'a trompé c'est qu'il ne reprenait pas le schéma que je t'avais donné.
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:37 | #


oui en effet ton algo était + court mais je n'y ai pas tout compris le mien est + intuitif
sinon où est passé le 2 dans tout ca
Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:43 | #


Il n'y a pas toujours de 2 dans une liste

Je vais essayer de détailler mieux l'algorithme.
Au début, on prend la première valeur, puis on parcourt la liste jusqu'à ce que l'on tombe sur une plus petite. À ce moment, on inverse les deux. Ensuite, on prend la première valeur (la nouvelle), et on recommence.
Si aucune valeur dans la liste n'est plus petite, ça veut dire que la première est la plus petite, donc elle est à sa place.
On recommence donc avec une liste réduite à partir de la deuxième valeur.
La boucle continue tant que toutes les valeurs ne sont pas à leur place, c'est-à-dire tant que la valeur sélectionnée n'est pas la dernière.
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:46 | #


ok c'est plus clair merci
Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 15:51 | #


Je viens de voir que l'algorithme du tri bulle est celui que tu as proposé à l'origine, que j'ai confondu avec ma variante.
Désolé
Darkysun Hors ligne Membre Points: 1747 Défis: 52 Message

Citer : Posté le 19/04/2014 15:53 | #


??? pas de quoi être désolé
tu veux dire que j'ai trouvé le vrai algo du tri bulle tout seul en un seul essai !!!
Si je ne réponds pas à un post depuis trop longtemps : envoyez-moi un message pour me le rappeler !




Cartix Hors ligne Membre Points: 2748 Défis: 98 Message

Citer : Posté le 19/04/2014 16:03 | #


De toute façon, c'est pas la peine de vous casser la tête pour améliorer un bête niaiseux.
Et il n'y a pas de fonctions sortA et sortD toute faite ?
Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 16:06 | #


Avoir un algorithme de tri sous la main peut être très utile.
Sinon Darkysun, si tu veux faire encore plus rapide, tu copies la partie de liste à trier dans une autre liste, que tu passes à SortA, puis tu recopies le résultat dans la liste d'origine.

@Cartix
Justement, elles ne permettent pas de trier une partie de liste comme voulu.
Alex_1186 Hors ligne Membre Points: 1215 Défis: 46 Message

Citer : Posté le 19/04/2014 21:11 | #


Tu es sûr que c'est plus rapide?
Si on a que 5 valeurs à trier, le tri à bulle sur place me paraît plus économe...
Mais on s'en fiche je pense, parce que la vitesse n'est pas importante dans l'usage que Darkysun compte en faire!
Projets que je soutiens
Projets que je soutiens
Robscape 2 de Ray
Les tests vidéo de Marmotti
Mes projets
Mes projets
Une dizaine de projets top secrets...

Timeless Remix Airwolf
"And the dream will never die..."
Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 21:15 | #


Sur 5 valeurs, on peut avoir des doutes. Mais c'est sur la copie que ça se joue.
SortA est un algorithme de tri rapide (implementé dans la bibliothèque standard du C) et exécuté par le système, il n'y a donc aucun doute quant à sa supériorité niveau vitesse.
Alex_1186 Hors ligne Membre Points: 1215 Défis: 46 Message

Citer : Posté le 19/04/2014 21:18 | #


Tu sais, je l'ai déjà dit, la "rapidité" de l'algorithme n'est qu'asymptotique! Pour 5 valeurs si ça se trouve le plus rapide c'est le tri par sélection!
(on cherche le min, on le place en première position, puis le min de ce qui reste, on le place en deuxième position...
Je te laisse imaginer l'efficacité pour un million de valeurs! )
Projets que je soutiens
Projets que je soutiens
Robscape 2 de Ray
Les tests vidéo de Marmotti
Mes projets
Mes projets
Une dizaine de projets top secrets...

Timeless Remix Airwolf
"And the dream will never die..."
Lephenixnoir Hors ligne Administrateur Points: 20993 Défis: 143 Message

Citer : Posté le 19/04/2014 21:19 | #


Pour une même liste, de manière "générale" on peut penser que le quicksort est plus rapide.
Et puis il y a un gain immense au niveau du système.
1, 2 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2021 | Il y a 75 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd