Avant propos
A propos des tris...
Depuis l’avènement de l’informatique, les ordinateurs sont capables de traiter des quantités d’informations de plus en plus importantes. Actuellement, un simple ordinateur de bureau n’a rien à envier aux gros ordinateurs à peine plus âgés qu’eux. Mais la capacité des ordinateurs à effectuer des traitements de plus en plus importants n’est pas uniquement due à l’évolution physique des machines. Depuis l’avènement des premiers ordinateurs, le génie logiciel a également fortement évolué. Ainsi, nombre d’informaticiens cherchent à optimiser les algorithmes de traitement afin que ces derniers soient de plus en plus rapides et fiables.
Le traitement de données de masse pose le problème de leur classement. C’est pour cela que différentes méthodes de tris ont été développées. Ces pages proposent d’exposer les principales méthodes de tris connues à ce jour. L’étude des tris est un problème intéressant puisque c’est l’un des domaines de l’algorithmique qui a été le plus étudié. Cette étude permet également d’aborder de façon concrète les problèmes de complexité des algorithmes. Ainsi, pour un problème simple et unique, le tri d’un tableau de données, de nombreuses solutions existent. Malheureusement, seules quelques unes d’entre elles sont assez performantes pour supporter le traitement d’un nombre élevé de valeurs.
A propos de la présentation
Les différents algorithmes de tris vont être présentés de manière analogue. Tout d’abord, chaque algorithme sera expliqué, puis développé en pseudo langage. Ensuite, les algorithmes seront implémentés en Java, C, Caml et Objective Caml (OCaml) pour le tri de tableaux et puis Caml et OCaml pour le tri de listes. Enfin, une étude de la complexité de chaque algorithme tiendra lieu de conclusion. Tous les algorithmes sont implementés pour classer des nombres entiers, l’utilisateur pourra facilement adapter le code source au tri d’autres types de données, tel que des nombres réels, des chaines de caractéres...
L’utilisation de langages de programmation variés permettra au lecteur de se référer au(x) langage(s) qu’il connaît et éventuellement d’effectuer une comparaison entre le code de chacun des langages.
A propos de la complexité...
La complexité est évaluée en fonction d’une valeur représentative du calcul. Ici, ce sera en fonction du nombre de valeurs à classer. La complexité est notée sous forme de O(f(n)) (grand O de f(n)). Cela signifie que le temps de calcul est proportionnel à f(n). Le temps total T pour réaliser l’algorithme sera donc égal à T=k.t.f(n) où t est le temps élémentaire nécessaire pour faire une opération (dépend de la vitesse du processeur de l’ordinateur ou du calculateur), k un facteur constant de proportionnalité et f(n) le facteur de complexité dépendant de la valeur représentative du calcul.
Un algorithme n’est pas indéfiniment performant (sinon, il serait possible de réaliser des opérations en un temps nul). La logique veut que, pour classer n’importe qu’elle série de valeurs, il faut parcourir au moins une fois l’ensemble des valeurs (ne serais ce que pour constater que la série de valeurs est déjà classée). La lecture de n valeurs est linéairement proportionnelle au nombre de valeurs à lire. Donc, pour classer n valeurs, la complexité d’un algorithme ne sera jamais inférieure à la complexité de leur lecture, c’est à dire O(n).
A propos des tableaux et des listes
Un tableau peut se représenter comme un ensemble de cases, ou d’emplacements mémoire, adjacents. Il est ainsi possible d’accéder directement au contenu d’une ou plusieurs cases d’un tableau. Le seul inconvénient et que la taille d’un tableau est fixé lors de sa création, et que cette taille n’est plus modifiable dans la suite du programme.
Une liste ou une pile est un ensemble de cases non forcément adjacentes. Chaque élément d’une liste contient donc une valeur et l’adresse mémoire de l’élément suivant. Par conséquent, pour accéder au piéme élément d’une liste, il faut parcourir tous les éléments qui le précèdent ; en effet il est impossible de savoir, à priori, l’adresse mémoire du piéme élément. Mais si les listes sont beaucoup moins faciles à manipuler que les tableaux, elles ont un énorme avantage : elles sont extensibles à tout moment puisque les cases mémoires ne sont pas forcément adjacentes.
Accueil des algorithmes de tri
Article suivant : la fonction échanger
