TIGCCLIB: Bug dans stdio ??? - Page 2

godzil
: N'empeche que les LC sont dans beaucoup de cas plus adapté que les tableau et/ou tableau de pointeurs.

Mais pas pour un tri!

tu fait un tri avec les donnée que tu a déja !

Tu va pas faire un tableau de pointeur spécialement pour faire un tri alors que tu a deja une liste chainée !

Pourquoi pas? C'est faisable en O(n). Le tri lui-même est en O(n ln(n)) minimum.

godzil :
le tri d'une liste chainé pour des donnée complexe peut etre largement plus rapide aussi

Kevin
: Non, le tableau de pointeurs est plus efficace.

lol !
Pour le tri par types d'Einstein, j'ai employé une liste chaînée. Le tri s'effectue en O(n). Qui dit mieux ? Alors évite de dire des bêtises

Thibaut > Ton tri s'effectu dans des condition bien particulieres, on ne peut pas le comparer a tout les cas, et surtout les généraux

Je veux simplement montrer à Kevin que "le tableau de pointeurs est [sous entendu toujours] plus efficace" n'est pas vrai.

et je suis bien d'accord sur se point

Et quel est l'ordre de vitesse du bubble sort (oui, je sais, ça n'est pas bien du tout) ? O(n^2), vu qu'il y a deux boucles imbriquées ? Si c'est ça, alors il faut minimiser n (faire plusieurs tris sur des portions plus petites plutôt qu'un tri sur un gros tableau (il faut probablement que les données s'y prêtent)...

Je n'ai jamais fait d'étude de complexité des algorithmes, et je ne suis pas sûr que je vais en faire cette année qui va commencer... Vive le MIAS !

Moi je vais en STPI (Sciences et Technologies pour l'Ingénieur) : on fait beaucoup plus d'informatique, beaucoup plus d'électronique, moins de chimie : le pied !
C'est aussi moins "bourrage de crâne" il semblerait.

Oui, c'est ca: O(n²)

Y'a un tri pour lequel personne n'a réussit à déterminer le temps d'exécution. Ca serait pas celui-là ?

Non, c'est le Shell Sort. Utilisé entre autres par TIGCCLIB.

XDanger
: Et quel est l'ordre de vitesse du bubble sort (oui, je sais, ça n'est pas bien du tout) ? O(n^2), vu qu'il y a deux boucles imbriquées ? Si c'est ça, alors il faut minimiser n (faire plusieurs tris sur des portions plus petites plutôt qu'un tri sur un gros tableau (il faut probablement que les données s'y prêtent)...

Et surtout ne pas utiliser cet algorithme affreux!

> C'est aussi moins "bourrage de crâne" il semblerait.
Pour ce qui est du bourrage de crâne pour moi, tu repasseras: je fais mes cours par correspondance. Le bourrage de crâne serait plutôt à mon avis plus en prépa qu'en MIAS...
Je sais très bien que ça n'est pas ce que je vais apprendre à l'école les deux premières années qui me rendra utilisable. Il faut donc que je bosse l'informatique à part...

> Et surtout ne pas utiliser cet algorithme affreux!
Bah, on commence par faire un truc qui marche, et on optimise après...
J'ai déjà transformé un bubble sort sur 1500 éléments en environ 25 bubble sorts sur un nombre variable d'éléments, <250 (c'est pour ceux-là qu'il faudrait faire plus efficace).
C'est forcément plus rapide, puisqu'on est en O(n²), si on divise n par k, on va avoir k fois plus de tris, mais k * (n/k)² = n²/k... Au pire, j'ai donc divisé le temps précédent par 6 (en fait, c'est plus que ça), j'ai donc changé d'ordre de grandeur...

J'ai dit que c'était MOINS bourrage de crâne.