Je suis en train de programmer une fonction pour un TI-Nspire, donc je ne peux pas utiliser les builtins depuis l'intérieur d'une fonction. Quel est l'algorithme le plus efficace pour trier une liste de nombres sans modifier la liste elle-même? (récursivité et list-fractionnement sont un jeu équitable, tout comme l'utilisation générale des mathématiques.)Tri fonctionnel efficace
Mergesort est simple, efficace et stable: diviser la liste, trier récursivement, et fusionner les résultats. Pour être plus précis, mergesort prend O (N log N), qui est asymptotiquement optimal. De plus, en pratique (avec les deux algorithmes modifiés pour trier les sous-listes courtes avec un tri spécifique), mergesort peut être un concurrent proche du quicksort modifié utilisé dans les bibliothèques standard C/C++. Edit: contrairement aux tris en place tels que le tri rapide et le tri par insertion, mergesort nécessite de la mémoire auxiliaire, et est plus simple à implémenter en copiant plutôt qu'en échangeant.
Si vous pouviez modifier la liste alors je suggère quicksort car il utilise moins de mémoire en moyenne, mais mergesort est certainement la solution à adopter dans ce cas. –
@Justin Peel: Notez également qu'une implémentation naïve du tri rapide deviendra facilement plus lente que le tri par fusion pour les données volumineuses. AFAIK, le tri rapide efficace signifie le tri rapide + le choix du pivot du cleaver + (peut-être) le repli sur le tri en tas (voir tri de l'intro). Sinon, dans mon expérience, le tri rapide pur ne fonctionne pas bien par rapport au tri par fusion. – Giorgio
Timsort est utilisé dans python et java SE 7. Il prend le meilleur du tri par fusion et du tri par insertion. Le tri par insertion est O (n^2) mais avec de petites listes de nombres c'est plus rapide que le tri par fusion!
Ainsi, vous pouvez l'utiliser comme un algorithme de tri générique comme indiqué here
n'a pas envie de tout lire, mais étant donné que vous avez dit qu'il faut fusionner et insérer le tri, et que les tris d'insertion modifient la valeur inplace, le timsort nécessite-t-il une modification in situ? – muhmuhten
Timsort est génial, mais je pense que c'est beaucoup plus compliqué que nécessaire pour obtenir un bon tri sur une calculatrice. –
Je suppose que vous avez essayé d'appeler 'SortA' sur une liste, mais la calculatrice ne vous laissera pas faire cela parce qu'il est en fonction? Soupir. Ce problème existe également sur la TI-68k. –
précisément le problème. la série 83 n'a pas ce problème, mais n'a pas non plus de passage d'argument intégré. – muhmuhten
Si cela aide, j'ai remarqué ces fonctions de tri sur ticalc.org: http://www.ticalc.org/archives/files/fileinfo/429/42964.html –