Salut à tous.
Combien existe-t-il de méthodes de tri actuellement ?
@+
Salut à tous.
Combien existe-t-il de méthodes de tri actuellement ?
@+
La question n'était pas que fait 6x9, mais bien la liste des méthodes de tri connue à ce jour.
En voici un extrait :
--> tri par insertion
--> tri à bulle
--> tri par sélection
--> tri rapide
--> tri fusion
--> tri arborescent
--> tri par partition
--> tri par shell
Ce que je recherche, c'est le nom de tris connus à ce jour, ainsi que leur algorithme.
@+
Il en existe énormément, mais tous les algorithmes ne sont pas applicables(*) à tous les cas. Notamment, il y a des algorithmes qui seront très performants sur des matrices creuses, mais très mauvais sur des matrices pleines, d'autres prévus pour les ordinateurs quantiques, d'autres qui seront plus orientés vers des gros volumes de donnés, etc...
(*) : bien sur, tu peux toujours appliquer un algo à un cas pour lequel il n'est pas adapté, mais les performances peuvent être désastreuses. Par exemple, quick-sort est mauvais sur les données déjà triées (ca tend vers O(n^3) si mes souvenirs sont bons), et ce n'est pas pour rien que dans certains cas tu vois une répartition random du tableau avant de faire un tri, pour être presque certain de ne pas tomber dans le cas O(n^3).
Je ne cherche pas à appliquer une quelconque méthode de tri, mais juste à faire le recensement de ce qui existe déjà.
Entre autre, la complexité de l'algorithme, les performances, l'originalité de l'approche, de quoi elle dérive, la taille mémoire nécessaire ...
Tu as quelques éléments de réponse sur wikipedia fr : https://fr.wikipedia.org/wiki/Algorithme_de_tri
Et plus sur wikipedia en anglais : https://en.wikipedia.org/wiki/Sortin...ing_algorithms
Que tu manque-t-il ? Une liste exhaustive est impossible à établir, il y en a trop
Salut gangsoleil.
Et où peut-on trouver les algorithmes qui sont associés à ces tris ?
Quel est l'algorithme de tri le plus rapide ?
@+
Dans quel cas ? Certains fonctionnent mieux quand les données sont presque triées, d'autres quand elles sont dans l'ordre inverse, etc. Le tri rapide est, en moyenne, l'un des algorithmes les plus rapides, mais sans certitude (complexité en O(n log n) en moyenne, O(n^2) dans le pire cas) ; le tri par tas est asymptotiquement idéal, avec une complexité de O(n log n) dans le pire cas, mais en pratique n'est pas toujours le plus rapide.
Sans oublier que toute combinaison d'algorithmes de tri peut faire un nouvel algorithme de tri plus rapide (par exemple, un tri par fusion, appliqué récursivement jusqu'à une certaine taille de blocs à fusionner, où un autre algorithme est utilisé), comme https://en.wikipedia.org/wiki/Timsort.
Bonjour,
il y a deux grandes catégories de tri de tableau (par extension de liste même si c'est un poil différent) :
- les tris par comparaisons entre éléments (la majorité des tris «classiques» que l'on apprend)
- les tris sans comparaisons entre éléments (radix sort, bucket sort, bogo sor, spaghetti sortt)
Il est important de commencer à faire cette différence car sinon les complexité temporelle ne signifieront rien. Dans le premier cas, les complexités temporelles sont donnée en nombre de comparaisons/échanges entre éléments ; dans le second cas elles sont simplement données en terme d'opérations élémentaires. C'est pourquoi on ne se trompe pas en disant que les algo de la première catégorie ne pourront jamais faire mieux que O(n lg n) (comparaisons/échanges sous-entendu) tout en disant que radixsort est un tri en O(n) (même si là on sous entend aussi que les nombres traités ne sont pas arbitrairement grands, une constante cachée étant l'ordre de grandeur du plus grand élément).
Maintenant il faut aussi se dire qu'il n'existe pas un algorithme universel de tri qui battrait tous les autres tout le temps. Pour chaque algorithme et pour chaque implémentation on pourra toujours trouver une entrée pour laquelle une autre implémentation d'un autre algorithme sera «meilleure» pour autant que tu donnes un sens à «meilleur».
Il existe aussi des algorithme de tri qu'on ne reconnaît pas en tant que tel. Par exemple si tu n'as que 3 éléments à placer en ordre tu ne vas pas faire un quicksort, tu vas simplement faire quelques if et le tour est joué. Un autre exemple est la recherche d'un chemin hamiltonien qui peut être associé à un algorithme de tri car on crée de facto un ordre.
C'est un sujet très vaste.
Salut à tous.
C'est justement pour ça que je pose la question.Envoyé par picodev
Non pas que je sois totalement ignare en ce domaine, mais plutôt pour faire une mise à niveau de mes connaissances.
Il y a des tris que je n'ai jamais entendu parlé. Par exemple, les tris :
--> spaghetti
--> idiot
--> shaker
--> peigne
--> de batcher
--> cocktail
--> tim sort
--> par tas
--> intro sort
--> smooth sort
Il est fort possible que je les connaisse sous un autre nom ! Mais difficile de se faire une opinion sans avoir l'algorithme.
De plus, n'avons-nous pas dans ces tentatives multiples, des exercices de style qui n'ont d'intérêt que de laisser le nom de leut auteur à la postérité.
La question n'est pas si idiote que cela car on ne trouve pas toujours ce que l'on cherche, même avec google.Envoyé par dourouc05
Je prends au hasard le tri spaghetti. Bien que je connaisse la programmation spaghetti, je suppose que cela n'a aucun rapport ni avec les spaghettis, et encore moins avec l'usage abusif que l'on faisait du "goto" dans les langages dits non structurés.
Ce qui m'intéresse, ce sont les tris internes, c'est-à-dire un tableau mémoire qui va nous servir à effectuer par la suite des rechercher.
Prenons l'exemple d'une tableau totalement vide au départ. J'insère les éléments étape par étape.
Quel est la meilleure façon de procéder ?
1) de faire le tri du tableau quand celui-ci sera totalement rempli ?
2) de faire le tri à chaque nouvelle insertion dans le tableau ?
Autre approche. Puisque je dois faire une recherche dans un tableau, est-il encore nécessaire de faire un tri ?
Je pense aux tables associatives, c'est-à-dire sur l'adressage calculée.
Qu'en pensez-vous ?
@+
Des fois, il ne faut pas chercher à comprendre
Le problème du tri par tas (Heapsort), c'est qu'il nécessite beaucoup de déplacements et en majorité, entre des cases éloignées successibles de provoquer des "cache misses" (par exemple, on déplace toujours la racine (la première valeur) vers la fin)
Donc, Edsger Dijkstra a créé le tri Smoothsort pour palier ces inconvénients: Smoothsort Demystified, basé non pas sur un tas mais sur "Leonardo Trees" (<- prends de l'aspirine, ça tape fort )
- J'imagine que dans tes recherches, tu es tombé sur ce lien : https://en.wikipedia.org/wiki/Spaghetti_sort, où on liste une 40aine de méthodes de tris.
- Pour préparer des données et optimiser les recherches dans ces données, l'idéal n'est pas de trier les données, mais de créer un index. Regarde du côté de l'index B-tree.
- 42, ce n'est pas égal à 6x9, mais à 6x7 .
Inculte .
Salut à tous.
Et pourquoi donc ?Envoyé par foetus
@ foetus : le tri smoothsort ressemble beaucoup au tri arborescent. En quoi est-il meilleur que le tri arborescent ?
Par contre, je ne comprends pas bien ce qui caractérise le tri par tas vis-à-vis du tri arborescent.
@ tbc92 : oui, en effet, j'ai trouvé ce lien où il est question du tri spaghetti.
Mais j'ai plutôt préféré cet autre lien : http://www.pourlascience.fr/ewb_page...ttis-18987.php
D'après ce que j'ai compris, cela consiste à rechercher le nombre le plus grand, à l'extraire de la liste et à recommencer l'opération sur la liste des non classé.
En quoi, cette méthode de tri est plus pertinente ?
Si vous faites cette remarque, c'est que vous ne connaissez rien à "La grande question sur la vie, l'univers et le reste".Envoyé par tbc92
C'est tiré de l'oeuvre de "Douglas Adams Le Guide du voyageur galactique".
A la réponse "42" de gangsoleil, j'ai répondu "6x9" en faisant un clin d'oeil à l'ouvre de Douglas Adams.
Personne n'a répondu à mes des questions :
Il est fort possible que la réponse se trouve dans la remarque de tbc92 :Envoyé par Artemus24
Mais je ne comprends pas trop bien ce que vous entendez par "index" ? Ce terme est-il en relation avec les bases de données ?Envoyé par tbc92
Si c'est le cas, l'index est un fichier à part, qui contient un pointeur vers la page de la table où est stockée la valeur maximale de cette clef.
Comme vous devez vous en douter, cet index est trié sur la clef, pas toutes les clefs car on stocke que la plus grande clef de la page où elle se trouve.
Si vous recherchez une clef et que cette clef est plus petite que celle de l'index, alors si elle existe, elle doit obligatoirement se trouver dans la page, pointé par l'adresse.
Quand je parle de l'adressage calculée (hash coding ), il s'agit de trouver une adresse à partir d'une clef disons alphabétique.
Il s'agit de fonction de hachage. Et l'on nomme cela des tables associatives.
@+
Salut foetus.
Pire que cela, je ne me suis jamais vraiment penché sur toutes les différences qui existe dans ces tris.Envoyé par Foetus
Comme beaucoup d'informaticiens, j'utilise quelques algorithmes que j'ai appris et rencontré dans mes différentes missions quand je travaillais. (oui, je suis à la retraite).
Si vous me le dites, c'est que je ne suis pas le seul à ne pas comprendre l'intérêt de ce tri.
@+
Il faut faire la différence entre la structure de donnée + les algos et une implémentation spécifique.
Ce qu'on attend d'une hashtable est une complexité temporelle moyenne et/ou amortie constante O(1) et en O(n) dans le pire des cas pour les opérations de recherche, d'insertion et de délétion, n étant le nombre d'éléments que contient la table, la complexité temporelle étant en opérations élémentaires.
À la limite on ne demande pas plus. Si ton implémentation respecte ce cahier des charges alors tu es assuré de toutes les propriétés des hashtable.
Ensuite il y a les détails d'implémentation pour un langage particulier et parfois pour une plateforme particulière, voire pour des données particulières.
Si tu as une bonne fonction de hachage, avec peu de collisions alors la question ne se pose pas. Ta fonction de hachage te donne un id auquel tu accède en temps constant puis tu cherches dans une liste la clé demandée. Comme le taux de collision est faible que tu fasses une recherche binaire dans une liste que tu maintiens triée ou que tu tries avant la recherche c'est dérisoire … autant faire une recherche brute. Les performances ne se dégraderont que lorsque les collisions seront nombreuses.
Mais attention le fait de maintenir une liste triée a un coup de l'ordre de O(k log k) où k est le nombre moyen de collisions. Si tu tombes dans un cas dégénéré où k n'est plus négligeable face à n alors tu n'auras plus une hashtable car tex complexités temporelles s'effondreront, mais bon c'est le risque de maintenir une structure triée.
L'idée est vraiment de maintenir un taux de collision bas pour s'éviter justement d'avoir à maintenir un ordre.
Si, il y a un intérêt c'est une amélioration du tri par tas "Heapsort"
(je le redis en différent) Lorsqu'on construit un tas on va parcourir le tableau de gauche à droite. Mais on va faire des inversions de valeurs qui ne sont pas contiguës et donc peuvent entrainer des "cache misses".
Par comparaison, le tri rapide "Quicksort", et moins sujet aux "cache misses", parce qu'on compare successivement les valeurs.
Et ensuite, le tas construit, rebelote: on va ranger la racine (la première valeur) vers la fin.
Donc le tri "Smoothsort", va utiliser des "Leonardo Trees", parce que (c'est dit dans mon lien), c'est comme un tas mais à l'envers: en gros les feuilles sont plus à gauche et les racines plus à droite, donc plus dans un ordre chronologique
Salut à tous.
J'ai commencé par les tris les plus simples. Voici mon source écrit en 'C' :
Bien sûr, chaque tri donne le même résultat. J'aurai dû tester la performance, mais bon, ce n'est pas exactement ce que je cherche à faire.
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369 #include <stdlib.h> #include <stdio.h> /*********************/ /* */ /* Affichage */ /* */ /*********************/ void Afficher(const int *ptr, const int z, const int n) { int i; switch (z) { case 1: printf("Avant : "); break; case 2: printf("Après : "); break; } for (i=0; i<n; i++) printf("%d ", *(ptr+i)); printf("\n"); if (z == 2) printf("\n"); } /********************/ /* */ /* Echanger */ /* */ /********************/ void Echanger(int v[], const int i, const int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } /***********************/ /* */ /* Tri à Bulle */ /* */ /***********************/ void TriBulle(int v[], int n) { int flag; do { flag = 0; for (int i=0; i<n; i++) { if (v[i] > v[i+1]) { Echanger(v, i, i+1); flag = 1; } } n--; } while (flag); } /******************************************/ /* */ /* Tri Shaker (ou bidirectionnel) */ /* */ /******************************************/ void TriShaker(int v[], const int n) { int flag=1, iMin=0, iMax=n; while (flag) { flag=0; for (int i=iMin; i < iMax; i++) { if (v[i] > v[i+1]) { Echanger(v, i, i+1); flag = 1; } } iMax--; for (int i=iMax-1; i >= iMin; i--) { if (v[i] > v[i+1]) { Echanger(v, i, i+1); flag = 1; } } iMin++; } } /**********************/ /* */ /* Tri Peigne */ /* */ /**********************/ void TriPeigne(int v[], const int n) { int flag, iPas=n; do { flag=0; iPas /= 1.3; if (iPas < 1) iPas = 1; for (int i=0; i<=(n-iPas); i++) { if (v[i] > v[i+iPas]) { Echanger(v, i, i+iPas); flag = 1; } } } while (flag || iPas>1); } /*****************************/ /* */ /* Tri par Sélection */ /* */ /*****************************/ void TriSelection(int v[], const int n) { for (int i=0; i<=n; i++) { int iMin = v[i]; int iPos = i; for (int j=i+1; j<=n; j++) if (iMin > v[j]) { iMin = v[j]; iPos = j; } Echanger(v, i, iPos); } } /*****************************/ /* */ /* Tri par Insertion */ /* */ /*****************************/ void TriInsertion(int v[], const int n) { int j; for (int i=1; i<=n; i++) { int elem = v[i]; for (j=i; j>0 && v[j-1]>elem; j--) v[j] = v[j-1]; v[j] = elem; } } /*********************/ /* */ /* Tri Gnome */ /* */ /*********************/ void TriGnome(int v[], const int n) { int i=1; while (i <= n) { if (v[i-1] <= v[i]) { i++; } else { Echanger(v, i-1 , i); if (i > 1) i--; } } } /*********************/ /* */ /* Tri Shell */ /* */ /*********************/ void TriShell(int v[], const int n) { for (int iEcart=n/2; iEcart>0; iEcart/=2) { for (int i=iEcart; i<=n; i++) { for (int j=i-iEcart; j>=0 && v[j]>v[j+iEcart]; j-=iEcart) Echanger(v, j , j+iEcart); } } } /**********************************/ /* */ /* Tri Rapide (quicksort) */ /* */ /**********************************/ void TriRapide(int v[], const int iGauche, const int iDroite) { int i, iPivot; if (iGauche >= iDroite) return; Echanger(v, iGauche, (iGauche+iDroite)/2); iPivot = iGauche; for (i=iGauche+1; i<=iDroite; i++) if (v[i]<v[iGauche]) Echanger(v, ++iPivot, i); Echanger(v, iGauche, iPivot); TriRapide(v, iGauche, iPivot-1); TriRapide(v, iPivot+1, iDroite); } /**********************/ /* */ /* Tri Fusion */ /* */ /**********************/ void Fusion (int v[], const int iDeb, const int iMed, const int iFin) { int t[20]; for (int i=iDeb, j=iMed+1, k=0; k<=(iFin-iDeb); k++) { if ( i > iMed) { t[k] = v[j++]; } else { if ( j > iFin) { t[k] = v[i++]; } else { if (v[i] < v[j]) { t[k] = v[i++]; } else { t[k] = v[j++]; } }}} for (int k=0; k<=(iFin-iDeb); k++) { v[k+iDeb] = t[k]; } } /* ------------------------------------------------------------------------ */ void TriFusion(int v[], const int iDeb, const int iFin) { if (iDeb == iFin) return; int iMed = (iDeb + iFin) / 2; TriFusion(v, iDeb, iMed); TriFusion(v, iMed+1, iFin); Fusion(v, iDeb, iMed, iFin); } /********************************/ /* */ /* Procédure Principale */ /* */ /********************************/ int main(void) { int iTab01[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab02[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab03[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab04[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab05[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab06[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab07[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab08[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; int iTab09[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1}; printf("+---------------------+\n"); printf("| Tri à Bulle |\n"); printf("+---------------------+\n\n"); Afficher(iTab01, 1, 20); TriBulle(iTab01, 19); Afficher(iTab01, 2, 20); printf("+--------------------+\n"); printf("| Tri Shaker |\n"); printf("+--------------------+\n\n"); Afficher(iTab02, 1, 20); TriShaker(iTab02, 19); Afficher(iTab02, 2, 20); printf("+--------------------+\n"); printf("| Tri Peigne |\n"); printf("+--------------------+\n\n"); Afficher(iTab03, 1, 20); TriPeigne(iTab03, 19); Afficher(iTab03, 2, 20); printf("+---------------------------+\n"); printf("| Tri par Sélection |\n"); printf("+---------------------------+\n\n"); Afficher(iTab04, 1, 20); TriSelection(iTab04, 19); Afficher(iTab04, 2, 20); printf("+---------------------------+\n"); printf("| Tri par Insertion |\n"); printf("+---------------------------+\n\n"); Afficher(iTab05, 1, 20); TriInsertion(iTab05, 19); Afficher(iTab05, 2, 20); printf("+-------------------+\n"); printf("| Tri Gnome |\n"); printf("+-------------------+\n\n"); Afficher(iTab06, 1, 20); TriGnome(iTab06, 19); Afficher(iTab06, 2, 20); printf("+-------------------+\n"); printf("| Tri Shell |\n"); printf("+-------------------+\n\n"); Afficher(iTab07, 1, 20); TriShell(iTab07, 19); Afficher(iTab07, 2, 20); printf("+--------------------+\n"); printf("| Tri Rapide |\n"); printf("+--------------------+\n\n"); Afficher(iTab08, 1, 20); TriRapide(iTab08, 0, 19); Afficher(iTab08, 2, 20); printf("+--------------------+\n"); printf("| Tri Fusion |\n"); printf("+--------------------+\n\n"); Afficher(iTab09, 1, 20); TriFusion(iTab09, 0, 19); Afficher(iTab09, 2, 20); /*===========================*/ /* Fin du Traitement */ /*===========================*/ return 0; }
Pour l'instant, mes tris préférés sont ceux en récursivité.
@+
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager