Programmation : algorithme de tri en vb
r_requin6
Messages postés
2
Date d'inscription
dimanche 10 avril 2005
Statut
Membre
Dernière intervention
10 avril 2005
-
10 avril 2005 à 14:39
cs_AbriBus Messages postés 492 Date d'inscription jeudi 28 août 2003 Statut Membre Dernière intervention 25 avril 2007 - 11 avril 2005 à 05:02
cs_AbriBus Messages postés 492 Date d'inscription jeudi 28 août 2003 Statut Membre Dernière intervention 25 avril 2007 - 11 avril 2005 à 05:02
14 réponses
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 18:43
10 avril 2005 à 18:43
Bah ca depend quel genre de tri tu cherches... il y en a pas 200, je crois qu'il y en a que trois ou quatre...
le "Tri Bulle" est le plus simple je crois... ca consiste en une boucle TantQue. Dans la boucle, tu verifies que les nombres sont dans le bon ordre deux-a-deux (d'abord les 2 premiers puis les N° 2 et 3 etc...) s'il y a eut une inversion (ca c'est dans un If... Then) prend soin de fixer un booleen FinTri a False qui te permettra de sortir de ta boucle TantQue s'il vaut True.
il y en a un autre qui s'appelle le "QuickSort" mais je le connais pas... les autres j'en ai meme pas entendu parlé... je crois que mes competances mathematiques ne me permettraient pas de comprendre tout bien...
Voila... donc c'est pas le plus rapide mais c'est le plus simple... Le TriBulle !!
Bonne Prog !
AbriBulle
le "Tri Bulle" est le plus simple je crois... ca consiste en une boucle TantQue. Dans la boucle, tu verifies que les nombres sont dans le bon ordre deux-a-deux (d'abord les 2 premiers puis les N° 2 et 3 etc...) s'il y a eut une inversion (ca c'est dans un If... Then) prend soin de fixer un booleen FinTri a False qui te permettra de sortir de ta boucle TantQue s'il vaut True.
il y en a un autre qui s'appelle le "QuickSort" mais je le connais pas... les autres j'en ai meme pas entendu parlé... je crois que mes competances mathematiques ne me permettraient pas de comprendre tout bien...
Voila... donc c'est pas le plus rapide mais c'est le plus simple... Le TriBulle !!
Bonne Prog !
AbriBulle
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 18:55
10 avril 2005 à 18:55
Ha j'oubliais... il y en a un autre... celui que l'on appelle le "Tri Simple" mais c'est un peu laid je trouve:
tu ranges tes nombres dans un tableau, tu declares un aute tableau de meme taille... puis tu parcourt le tableau autant de fois que necessaire en deplacant le plus petit des nombre de ton tableau a trier vers ton tableau trier... (donc tu vide un tableau non trier pour en remplir un autre dans un ordre defini)... mais j'avais fait un prog en Vb pour comparer ces deux methodes...; c'est fout ce que les prf peuvent demander parfois... bref pas la peine de parler du resultat
Voila... celui la c le Tri Simple
AbriBus
tu ranges tes nombres dans un tableau, tu declares un aute tableau de meme taille... puis tu parcourt le tableau autant de fois que necessaire en deplacant le plus petit des nombre de ton tableau a trier vers ton tableau trier... (donc tu vide un tableau non trier pour en remplir un autre dans un ordre defini)... mais j'avais fait un prog en Vb pour comparer ces deux methodes...; c'est fout ce que les prf peuvent demander parfois... bref pas la peine de parler du resultat
Voila... celui la c le Tri Simple
AbriBus
Gobillot
Messages postés
3140
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
11 mars 2019
34
10 avril 2005 à 19:05
10 avril 2005 à 19:05
tri à bulles, tri par insertion, tri par sélection, tri de Shell, tri Quicksort, tri Lomuto, tri Dijsktra, tri Hybrid, tri Wainwright, tri fusion, tri par monceau, tri par radicaux, tri compteur, tri par FDM, etc ...
il y en a pas 200, il y en a des tonnes
Daniel
il y en a pas 200, il y en a des tonnes
Daniel
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 21:26
10 avril 2005 à 21:26
Salut Gobillot,
(wow... 1215 msg... ca faisait un petit moment que je t'avais pas vu lol )
Bah vas y, informe nous sur les algos
(wow... 1215 msg... ca faisait un petit moment que je t'avais pas vu lol )
Bah vas y, informe nous sur les algos
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Gobillot
Messages postés
3140
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
11 mars 2019
34
10 avril 2005 à 21:33
10 avril 2005 à 21:33
le tri dichotomique, le tri par la méthode de l'arbre, le tri par les 2 bouts, le tri par monotonie, etc ...
lequel tu veux, je les connais pas tous.
'TRI DE SHELL:
Sub Tri_Shell_Metzner(ByVal Nb_Element As Long, Tableau() As Variant, ByVal Sens As Boolean)
' le paramètre Nb_Element correspond au nombre d'éléments du tableau, sa valeur n'est donc pas modifiée
' le paramètre Tableau() est le tableau à trier, il est modifié puis retourné
' le paramètre Sens est vrai pour un tri croissant
Dim Ecart As Long
' Ecart représente la division du tableau
Dim I As Long
Dim J As Long
' I et J sont des variables intermédiaires utilisées pour les compteurs de boucles
Dim Permut As Boolean
' Permut est un flag contrôlant que l'élément à classer a été permuté
Dim Ligne_Tampon As Variant
' Ligne_Tampon est une variable intermédiaire utilisée pour la permutation d'éléments
' On définit l'écart d'origine
Ecart = Nb_Element \ 2
Do While Ecart <> 0
For I = 1 To Nb_Element - Ecart
J = I
Permut = True
Do While J > 0 And Permut
Permut = False
If (Tableau(J) > Tableau(J + Ecart) And Sens) Or (Tableau(J) < Tableau(J + Ecart) And Not Sens) Then
Ligne_Tampon = Tableau(J)
Tableau(J) = Tableau(J + Ecart)
Tableau(J + Ecart) = Ligne_Tampon
Permut = True
J = J - Ecart
End If
Loop
Next I
' On redivise
Ecart = Ecart \ 2
Loop
End Sub
Daniel
lequel tu veux, je les connais pas tous.
'TRI DE SHELL:
Sub Tri_Shell_Metzner(ByVal Nb_Element As Long, Tableau() As Variant, ByVal Sens As Boolean)
' le paramètre Nb_Element correspond au nombre d'éléments du tableau, sa valeur n'est donc pas modifiée
' le paramètre Tableau() est le tableau à trier, il est modifié puis retourné
' le paramètre Sens est vrai pour un tri croissant
Dim Ecart As Long
' Ecart représente la division du tableau
Dim I As Long
Dim J As Long
' I et J sont des variables intermédiaires utilisées pour les compteurs de boucles
Dim Permut As Boolean
' Permut est un flag contrôlant que l'élément à classer a été permuté
Dim Ligne_Tampon As Variant
' Ligne_Tampon est une variable intermédiaire utilisée pour la permutation d'éléments
' On définit l'écart d'origine
Ecart = Nb_Element \ 2
Do While Ecart <> 0
For I = 1 To Nb_Element - Ecart
J = I
Permut = True
Do While J > 0 And Permut
Permut = False
If (Tableau(J) > Tableau(J + Ecart) And Sens) Or (Tableau(J) < Tableau(J + Ecart) And Not Sens) Then
Ligne_Tampon = Tableau(J)
Tableau(J) = Tableau(J + Ecart)
Tableau(J + Ecart) = Ligne_Tampon
Permut = True
J = J - Ecart
End If
Loop
Next I
' On redivise
Ecart = Ecart \ 2
Loop
End Sub
Daniel
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 21:42
10 avril 2005 à 21:42
si celui ci est le plus "efficace" alors c'est celui la qu'il faut ;)
Je suis super curieux... c'est apreciable de voir une aute methode que le tri bulle qui me faisait ch*** depuis 2 ans
Je suis super curieux... c'est apreciable de voir une aute methode que le tri bulle qui me faisait ch*** depuis 2 ans
Gobillot
Messages postés
3140
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
11 mars 2019
34
10 avril 2005 à 21:48
10 avril 2005 à 21:48
Comparaisons des différents algorithmes. Ci dessous, vous trouverez un tableau comparatif qui montre les temps, en millisecondes, pris par les différents algorithmes pour triés 10 000 nombres. La machine utilisée était équipée d'un processeur Athlon XP 2300 à 1.66GHz.
<HR align=center width="60%" height="1">
Algorithme
,
Temps (ms)
,
----
,
----
Bubble Sort
,
411.691
,
----
Bubble Insertion
,
287.979
,
----
Bubble Elevator
,
36.201
,
----
,
----
Insertion Sort
,
69.655
,
----
Selection Sort
,
352.927
,
----
,
----
Shell Sort
,
3.243
,
----
,
----
QuickSort
,
1.497
,
----
QuickSort Lomuto
,
1.454
,
----
QuickSort Dijsktra
,
2.405
,
----
QuickSort Hybrid
,
1.399
,
----
QuickSort Wainwright
,
2.180
,
----
,
----
Ex Situ Heap Sort
,
1.740
,
----
In Situ Heap Sort
,
2.240
,
----
,
----
Ex Situ Merge Sort
,
3.561
,
----
In Situ Merge Sort
,
11.026
,
----
,
----
Radix Sort 4 (compact)
,
1.403
,
----
Radix Sort 4 (extern)
,
1.229
,
----
,
----
Counting Sort
,
0.842
,
----
,
----
ProxMap Sort
,
0.701
<HR align=center width="60%" height="1">
Les algorithmes de tris sont montrés dans l'ordre approximatif de performance et de familles. On a d'abord les tris à bulle, dont le tri de Shell est le dernier représentant, la famille des Quicksorts, et des autres tris en O(n lg n), suivi des tris par transformation d'adresse.
D'après le tableau, on voit immédiatement le fossé qui sépare les tris à bulles des autres tris. Le tri à bulles de base est particulièrement pathétique, surtout lorsqu'on le compare aux tris O(n lg n) et aux tris par transformation d'adresse qui sont O(n).
Les tris par transformation d'adresse, bien que les plus rapides, sont d'application restreinte. Le tri par radicaux, ou radix sort, demande que les clefs aient des valeurs numériques, et la généralisation aux chaînes de caractères n'est pas triviale et rend l'algorithme nettement moins attrayant. Le tri compteur nécessite aussi un ensemble de clefs distinctes assez petites pour être utilisable. Sinon, la structure de données nécessaire pour maintenir les comptes excède rapidement la taille du tableau à trier. Le même type de conclusion est aussi valable pour le tri par fonction de distribution cumulative, ou
proxmap sort
<HR>
Il faut toutefois moduler les résultats chronométrés en fonction de la machine utilisée, du compilateur, du système d'exploitation, etc. En effet, sur une même machine, la qualité du code généré par différents compilateurs peut varier substanciellement.
Daniel
<HR align=center width="60%" height="1">
Algorithme
,
Temps (ms)
,
----
,
----
Bubble Sort
,
411.691
,
----
Bubble Insertion
,
287.979
,
----
Bubble Elevator
,
36.201
,
----
,
----
Insertion Sort
,
69.655
,
----
Selection Sort
,
352.927
,
----
,
----
Shell Sort
,
3.243
,
----
,
----
QuickSort
,
1.497
,
----
QuickSort Lomuto
,
1.454
,
----
QuickSort Dijsktra
,
2.405
,
----
QuickSort Hybrid
,
1.399
,
----
QuickSort Wainwright
,
2.180
,
----
,
----
Ex Situ Heap Sort
,
1.740
,
----
In Situ Heap Sort
,
2.240
,
----
,
----
Ex Situ Merge Sort
,
3.561
,
----
In Situ Merge Sort
,
11.026
,
----
,
----
Radix Sort 4 (compact)
,
1.403
,
----
Radix Sort 4 (extern)
,
1.229
,
----
,
----
Counting Sort
,
0.842
,
----
,
----
ProxMap Sort
,
0.701
<HR align=center width="60%" height="1">
Les algorithmes de tris sont montrés dans l'ordre approximatif de performance et de familles. On a d'abord les tris à bulle, dont le tri de Shell est le dernier représentant, la famille des Quicksorts, et des autres tris en O(n lg n), suivi des tris par transformation d'adresse.
D'après le tableau, on voit immédiatement le fossé qui sépare les tris à bulles des autres tris. Le tri à bulles de base est particulièrement pathétique, surtout lorsqu'on le compare aux tris O(n lg n) et aux tris par transformation d'adresse qui sont O(n).
Les tris par transformation d'adresse, bien que les plus rapides, sont d'application restreinte. Le tri par radicaux, ou radix sort, demande que les clefs aient des valeurs numériques, et la généralisation aux chaînes de caractères n'est pas triviale et rend l'algorithme nettement moins attrayant. Le tri compteur nécessite aussi un ensemble de clefs distinctes assez petites pour être utilisable. Sinon, la structure de données nécessaire pour maintenir les comptes excède rapidement la taille du tableau à trier. Le même type de conclusion est aussi valable pour le tri par fonction de distribution cumulative, ou
proxmap sort
<HR>
Il faut toutefois moduler les résultats chronométrés en fonction de la machine utilisée, du compilateur, du système d'exploitation, etc. En effet, sur une même machine, la qualité du code généré par différents compilateurs peut varier substanciellement.
Daniel
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 22:49
10 avril 2005 à 22:49
Voila...
r_requin6> tu voulais des algos de tri... moi je t'en ai donner 2 dont un est à ne surtout pas utiliser (le Tri Simple)... et le second est donc "pathétique" mais bon, c'est dejà du tri lol...
(Bubble Sort. 411.691) LOL. Bref, d'apres ce que j'ai lu ici, je confirme bien ce que je disais dons mon premier post, je crois bien que la vrai limite en ce qui me concerne n'est pas ma capacité a saisir des algoritmes informatiques mais plutot a saisir des algoritmes MATHEMATIQUES...
Comme j'aimerais avoir du talent pour les maths...
AbriBulle (peut pas abriter autre chose que des bulles)
r_requin6> tu voulais des algos de tri... moi je t'en ai donner 2 dont un est à ne surtout pas utiliser (le Tri Simple)... et le second est donc "pathétique" mais bon, c'est dejà du tri lol...
(Bubble Sort. 411.691) LOL. Bref, d'apres ce que j'ai lu ici, je confirme bien ce que je disais dons mon premier post, je crois bien que la vrai limite en ce qui me concerne n'est pas ma capacité a saisir des algoritmes informatiques mais plutot a saisir des algoritmes MATHEMATIQUES...
Comme j'aimerais avoir du talent pour les maths...
AbriBulle (peut pas abriter autre chose que des bulles)
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
10 avril 2005 à 22:55
10 avril 2005 à 22:55
c'est quoi le "Quick Sort Hybrid"... enfin, le principe tout du moins... tu sais ?
Gobillot
Messages postés
3140
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
11 mars 2019
34
10 avril 2005 à 23:02
10 avril 2005 à 23:02
L'algorithme hybride. Quicksort, peu importe l'algorithme de partition, va chercher à sous-diviser le tableau jusqu'à ce qu'on arrive à un tableau de taille dégénérée; ce qui veut aussi dire qu'un algorithme de partition passablement compliqué pourrait être appliqué à un ou deux éléments. En fait, pourquoi ne pas trier un tableau suffisament petit avec un autre algorithme ? Rappelez vous de la remarque selon laquelle un algorithme en O(n2) n'est pas forcément mauvais. En effet, dépendemment de la complexité d'implémentation, un petit algorithme en O(n2) pourrait battre un algorithme en O(n lg n) pour de petits n. Par exemple, ici, le tri à bulle « ascenseur », vous pourrez expérimenter avec d'autres algorithmes.
<HR>
ce qui entraine que le Tri à Bulles n'est pas rejeté complétement.
Abribus a encore toutes ses chances.
Daniel
<HR>
ce qui entraine que le Tri à Bulles n'est pas rejeté complétement.
Abribus a encore toutes ses chances.
Daniel
r_requin6
Messages postés
2
Date d'inscription
dimanche 10 avril 2005
Statut
Membre
Dernière intervention
10 avril 2005
10 avril 2005 à 23:38
10 avril 2005 à 23:38
Merci bcp tt le monde!
r_requin6
r_requin6
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
11 avril 2005 à 01:02
11 avril 2005 à 01:02
lol... merci Gobillot pour relativiser mon incompetance dans ce domaine... cette discution resume exactement ce que mes profs de math ont pu me dire 10 années durant...
"vous n'etes pas désagréable mais votre niveau en math est pathétique... pas completement innexistant mais particulierement limité"
Tout ceci vient me fait me poser une question (je me le permet car r_requin6 semble avoir fermer le topic) le BTS informatique option developpement d'application (dont le niveau de math est plus que pathétique a l'echelle d'un enseignement puisque le plus compliqué doit porter sur les matrices) n'a t il aucune valeur dans le monde de l'entreprise...?
"vous n'etes pas désagréable mais votre niveau en math est pathétique... pas completement innexistant mais particulierement limité"
Tout ceci vient me fait me poser une question (je me le permet car r_requin6 semble avoir fermer le topic) le BTS informatique option developpement d'application (dont le niveau de math est plus que pathétique a l'echelle d'un enseignement puisque le plus compliqué doit porter sur les matrices) n'a t il aucune valeur dans le monde de l'entreprise...?
cs_Bob Langlade
Messages postés
2
Date d'inscription
mardi 6 janvier 2004
Statut
Membre
Dernière intervention
11 avril 2005
11 avril 2005 à 02:22
11 avril 2005 à 02:22
En vb.net <?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" /><st1:PersonName w:st="on" ProductID="la méthode Array.Sort">la méthode Array.Sort</st1:PersonName>(MonTableau) semble assez rapide et très simple à mettre en œuvre.<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Bob Langlade
Bob Langlade
cs_AbriBus
Messages postés
492
Date d'inscription
jeudi 28 août 2003
Statut
Membre
Dernière intervention
25 avril 2007
5
11 avril 2005 à 05:02
11 avril 2005 à 05:02
bah oué mais ce qui est drole, c'est de l'ecrire soi meme la fonction (ou procedure) .Sort
Ceci dit... c'st bon a savoir... pour les truc rapide
Ceci dit... c'st bon a savoir... pour les truc rapide