Développement logiciel - Comparaison algorithmiques en C++
L'objectif de ce projet est de découvrir différents algorithmes de tris et la comparaison de ceux-ci. En l'occurrence, ces algorithmes doivent trier différents tableaux de valeurs, dans l'ordre arithmétique croissant. On dispose de différents tableaux :
- Un tableau généré aléatoirement
- Un tableau presque trié, chaque élément est soit à la bonne place, soit à une place d'écart (e. g. 1 3 2 4 6 5 8 7 9 10)
- Un tableau dont seuls les deux premiers éléments sont inversés (e. g. 2 1 3 4 5 6 7 8 9 10)
- Un tableau presque trié également, le premier et le dernier élément sont inversé (e. g. 10 2 3 4 5 6 7 8 9 1)
- Et enfin un tableau presque trié, mais ce sont ici les deux derniers éléments qui sont échangés (e.g. 1 2 3 4 5 6 7 8 10 9)
Caractéristiques techniques du projet
Le travail étant réalisé de nouveau en binôme, nous avons de nouveau utilisé GitHub, permettant la réalisation de différents algorithmes de tri simultanément. Nous avons pu réaliser 10 algorithmes de tri dans le temps limité de 12 heures.
Les algorithmes de tri ont été codés en C++, on a donc utilisé de nouveau Visual Studio. Nous devions exporter des données de nombre de comparaisons selon le type de tableau trié, et selon l'algorithme de tri employé.
En plus d'utiliser Word pour le rendu, nous avons également employé Excel afin d'exploiter les données exportées par le logiciel. On a ainsi analysé les données avec des graphiques pour afficher le nombre de comparaison, selon le type de tableau trié et sa taille, permettant de mettre en évidence quel est le degré de complexité de l'algorithme de tri.
Compétences acquises
Au cours de ces 12 heures imparti, nous avons pu atteindre la fin du sujet. En plus des algorithmes de tri "obligatoires" dans le sujet, nous avons pu intégrer 6 algorithmes supplémentaires.
La gestion de fichiers en sortie, et les algorithmes de tri en général étaient les compétences clefs travaillées dans cette SAE d'un point de vue algorithmique. Étant donné que les différents algorithmes de tri étaient déjà quasiment écrits, en pseudo-code tout du moins, il ne restait qu'à les réécrire en C++.
Le compte rendu était donc important, en particulier les graphiques sur Excel, et la présentation Word. Il y avait également des connaissances et savoirs mathématiques impliqués, notamment pour la complexité, qui était en N² ou N*ln(N), il fallait au minima savoir qu'est-ce que c'était.
Auto-critique du résultat
Ce projet portait à la fois sur des compétences en programmation, mais aussi des compétences mathématiques. Nécessairement, nous devions coder plusieurs algorithmes de tri, ce que l'on a bien réussi. Il fallait en faire un minimum parmi une liste, nous les avons tous fais, et en avons fait d'autres en plus. Mais aussi, il s'agissait de déterminer, selon les résultats, la complexité de ceux-ci, et selon les cas cités en début de cette page. Il n'y avait donc pas de démonstration nécessaire, nous aurions pu le faire pour certains très rapidement, c'est dommage. Pour autant, le compte-rendu était exhaustif et clair, pour fournir les données importantes de ce projet réussi.
Sources du projet
