Algorithme de tri; finales régionales

Bonjour,

J'suis dans mes petites révisions pour les finales régionales, et j'ai vu qu'il fallait savoir trier.

L'exercice exemple consiste en trier une très petite liste.

Dès lors, quel algorithme(s) de tri faut-il maîtriser? Est-ce qu'un bogosort ou un bubblesort peuvent suffire? Est-ce qu'il faut apprendre des algorithmes en O(n log n)? Des tris en place? Le smoothsort?

Parce que bon, trier 21 éléments, on peut faire ça en O(n!) sans trop de soucis...

Euh 21! C'est à peu près 10^20 ce qui fait déjà vraiment beaucoup ! Ce qui importe n'est pas d'apprendre un algorithme bêtement avec le problème qui lui est associé, il faut le comprendre et apprendre la méthode ! De plus, aux écrits de la demi-finale, on a assez souvent des sujets à propos des algorithmes de tri...

Oui effectivement je voulais plus dire O(n^2).

Et dans mon premier post, j'ai pas mis le bon lien, je l'ai maintenant modifié.

Soit dit en passant, ce n'est pas nécessaire d'apprendre non plus quarante algorithmes de tris. Si tu en connais déjà un en O(n lg n) c'est suffisant (et par connaître je veux dire comprendre & savoir refaire sans de difficultés), et ce n'est pas très compliqué. Si tu as des doutes, tu peux choisir quicksort ou mergesort qui sont tous les deux assez simples et utilisés en pratique (je pense que quicksort est plus utilisé, mais il a aussi plus d'améliorations plus subtiles que l'algo de base). Si tu connais déjà ceux-là, tu peux en voir d'autres pour ta culture générale, mais je ne pense pas que ce sera très impactant, et en tout cas c'est bien plus important de comprendre l'idée de l'algorithme que d'être capable de le refaire. Enfin, les algorithmes en autre chose que O(n lg n) sont uniquement utiles d'un point de vue pédagogique, mais n'ont – à priori – aucun intérêt (attention tout de même, certains algorithmes qui sont généralement présentés en O(n^2) peuvent être implémentés en O(n lg n), je pense notamment à insert sort avec insertion dichotomique).

N'y passe quand même pas trop de temps, si tu fais des exercices tu te rendras vite compte que ces algorithmes n'apparaissent pas très souvent, surtout qu'il existe des langages où ils sont déjà implémentés dans la librairie standard.

D'ailleurs, l'exercice exemple que tu donnes ne se résout pas en triant la liste (ou du moins, trier une liste se fait en temps au moins O(n lg n) alors que l'exo se résout en O(n)), même si vu la taille de l'input les solutions avec tri passent.