Travail en cours !
Contributions, commentaires et autres propositions d'améliorations bienvenues !
- Trouver un moyen de générer les données de départ avant les tests, e.g. pour avoir de plus gros tableau, ou de multiplier les tests.
- Selectionner quelques algorithmes, par exemple 4.
- Documenter les algorithmes sélectionnés.
- Tout mettre dans une base couchDB
Le but de ce kata est d'explorer différents algorithmes de tri.
- La page Wikipédia: https://fr.wikipedia.org/wiki/Algorithme_de_tri
- Explications et gif animés:
- 24 algorithmes de tri visualisés: https://www.youtube.com/watch?v=BeoCbJPuvSE
- Bubble Sort dance: https://www.youtube.com/watch?v=lyZQPjUT5B4
- Donnée de test (Open Data):
- http://sortbenchmark.org/ / http://www.ordinal.com/gensort.html
- Analysis and Testing of Sorting Algorithms on a Standard Dataset: https://ieeexplore.ieee.org/document/7280062/
Forker le repo
et créer une branche (git checkout -b username-langage par exemple git checkout -b ponsfrilus-nodejs, depuis votre fork). Faire ensuite une pull
request pour l'ajouter à ce repo en vous ajoutant comme contributeurs en bas de
ce fichier.
Le but de ce kata est de comprendre le fonctionnement des algorithmes de tri (par comparaisons) et de ne pas utiliser les fonctions "built-in" du langages. Il est nécessaire de chronométrer le temps nécessaire au tri de chaque tableau.
Les données à trier sont quatre tableaux générés par le script
./generate_data.sh, stoqués dans le fichier
generated_data.json. Les tableaux sont nommés de la
manière suivante (pour un appel ./generate_data.sh 500) :
data_random: des nombres de 1 à 500 mélangés ;data_nearly_sorted: des nombres de 1 à 500 mélangés par tranche de 10 ;data_reversed: des nombres de 500 à 1 ;data_few_unique: 5 fois les nombres de 100 à 199 mélangés.
En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. → https://fr.wikipedia.org/wiki/Tri_par_insertion
Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. → https://fr.wikipedia.org/wiki/Tri_rapide
Le tri à bulles ou tri par propagation est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide. → https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Le comb sort ou tri à peigne ou tri de Dobosiewicz est un algorithme de tri assez simple initialement inventé par Wodzimierz Dobosiewicz en 1980. Le comb sort améliore notablement les performances du tri à bulles, et peut rivaliser avec des algorithmes de tri réputés rapides comme le tri rapide (quick sort), le tri fusion (merge sort) ou le tri de Shell (Shell sort). → https://fr.wikipedia.org/wiki/Tri_%C3%A0_peigne
Le tri pair-impair opère en comparant tous les couples d'éléments aux positions paires et impaires consécutives dans une liste et, si un couple est dans le mauvais ordre (le premier élément est supérieur au second), il en échange les deux éléments. → https://fr.wikipedia.org/wiki/Tri_pair-impair
Le tri stupide consiste à vérifier si les éléments sont ordonnés et s'ils ne le sont pas à mélanger aléatoirement les éléments, puis à répéter l'opération. → https://fr.wikipedia.org/wiki/Tri_stupide
docker build -t epfldojo/katasort .
docker run -it --rm -v $(pwd):/work epfldojo/katasort ruby /work/generate_data.rb
docker run -it --rm -v $(pwd):/work epfldojo/katasort sh /work/bench_all_sort.sh
- langage → @epfl-dojo
- ...