paxal Le 09/10/2001 à 01:25 Un truc que je trouve dommage, c que vous ne cherchez des routines que pour les graphismes...
paxal Le 09/10/2001 à 01:25 t'en veux? j'en ai 4 à disposition si tu veux...
Bulles
Rapide
Fusion
et je sais plus
paxal Le 09/10/2001 à 01:25 Tri par selection
On cherche le plus petit élément de t[1] à t[n] et on l'échange avec t[1]; puis on cherche le plus petit élement de t[1] à t[n] que l'on échange avec t[1] et ainsi de suite.
Complexité en n^2/2
Tri par insertion
On trie le tableau de proche en proche: si le tableau est trié de 1 à k, alors oin insère l'élément (k+1) parmi les k premiers; ainsi le tableau est trié jusqu'à l'élément k+1.
Complexité:
- n^2/2 dans le pire des cas
- n dans le meilleur des cas
- n^2/4 en moyenne
Tri Fusion (merge sort)
Si le tableau a une taille supérieure à 1, on le divise en deux sous-tableaux de taille E(n/2) et E((n+1)/2), que l'on trie récursivement, puis que l'on fusionne.
Complexité en n.log n
Tri Rapide (quick sort)
On trie le tableau grâce à un pivot: on prend x le premier élément et on réarrange le tableau en deux classes: Ai > x et Ai <= x. Chaque sous tableau est alors trié récursivement.
Complexité:
- n.log n dans le meilleur des cas
- n^2 dans le pire des cas
- n.log n en moyenne
Il y a aussi le shell sort. Cf. les sources de qsort de TIGCCLIB. (Et non, ce n'est pas un quick sort, le nom est juste là pour la compatibilité avec les sources en C ANSI. Le shell sort est plus petit et n'est pas plus lent d'une manière significative que le quick sort pour les petits arrays comme on les utilise sur TI-89/92+, c'est pour ça que Zeljko Juric l'a choisi.)
Moi j'en connais qui est super, il trie les tableau seulement avec des addition et oui c'est possible et rapide ...
pour les algos std, je vais m'acheter un book que j'ai vu chez eyrolles, des que j'ai fini programmation "systeme en C sous Linux" et "GTK+" qui sont 2 paves de 900 pages...
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay
"tri par addition"? Moi, j'appellerais cela "tri par compte d'éléments". Et ça ne marche qu'avec des données pour lesquelles on peut utiliser une table. Je vois mal quelqu'un utiliser ce genre d'algorithme pour un tableau de unsigned longs... Et pour des chaînes de caractères, on peut l'oublier complètement.
[edit]Edité par Kevin Kofler le 07-10-2001 à 21:56:10[/edit]
Miles Le 09/10/2001 à 01:25 Le tri par comptage n'est pas un tri, puisqu'il y a des infos supplémentaires.
En effet, le meilleur coût que l'on puisse trouver est en n*ln(n), donc sbibi, il faut que tu prenne mergesort, mais implenté correctement, comme l'allocation doit être dynamique, il ne faut pas se planter, sinon autrement, utilise quicksort.
paxal Le 09/10/2001 à 01:25 En général, une méthode de tri ne dépasse pas n.log n, après ce sont des réultats à une constante près, voire à un terme en n près, donc pour mieux réussir, il faut regarder de plus près et comparer les différents algorithmes
Oui, le "tri par addition" ne trie rien du tout. C'est un algorithme de reconstruction d'une liste ordonnée à partir de la distribution des fréquences d'une liste non ordonnée. Et ça présuppose qu'on puisse faire une distribution des fréquences et que les données y contenues suffisent pour reconstruire une liste ordonnée. (Un contre-exemple: si on a des structures contenant un ID et d'autres données, la distribution des fréquences du ID ne nous permettra pas de reconstruire une liste ordonnée de structures.)
[edit]Edité par Kevin Kofler le 09-10-2001 à 01:23:34[/edit]
dites moi ce que vous pensez de ça !
vs avez vu la quantité de docs!!!
