Voici 3 algo trouvés grâce à Google (le nouveau meilleur ami de l'homme), c'est dans un autre language, mais facilement adaptable... Je te laisse le soin de l'adapter et de mettre le tous dans la section Script GML après...
Tri d'un tableau De nombreux algorithmes ont été proposés et étudiés pour résoudre le problème du tri, qui se présente fréquemment dans les problèmes de gestion de données : par exemple, on dispose d'un annuaire alphabétique des abonnés au téléphone, et on veut produire un annuaire classé par adresses. On présentera seulement trois algorithmes : le tri par insertion, de type incrémental, puis le tri par fusion et le tri rapide, tous deux de type << diviser pour régner >>.
Le tri par insertion procède de façon incrémentale, à la manière d'un joueur de carte qui range les cartes, au fur et à mesure qu'il les reçoit, à leur place parmi les précédentes.
- Code:
-
static void triInsertion(int[] t) {
for (int j=1; j<t.length; j++) {
int x = t[j];
int i = j-1;
// x doit être inséré dans le tableau ordonné 0..j-1
while (i>=0 && t[i]>x) {
t[i+1] = t[i];
i = i-1;
}
t[i+1] = x;
}
}
Tri par fusion En appliquant la méthode << diviser pour régner >> au problème du tri d'un tableau, on obtient facilement le tri par fusion (en anglais, mergesort) : on divise une table de longueur n en deux tables de longueur n/2, on trie, récursivement, ces deux tables, puis on fusionne les tables triées. Comme la fusion de deux tables ordonnées de longueur n/2 se fait en , l'équation de complexité est , dont la solution est en . Ce tri est implémenté dans les fonctions Collections.sort(List l) et Arrays.sort(Object[] t) de l'API, pour trier respectivement des listes et des tableaux d'objets. Voici une version optimisée de ce tri. Pour trier un tableau t, on commence par en créer une copie c, puis on appelle la fonction récursive triFusion() qui écrit dans t le résultat du tri de c ; chaque invocation récursive échange le rôle des tableaux source et destination :
- Code:
-
static void triFusion(Object[] t) {
Object[] copie = (Object[])t.clone();
triFusion(copie, t, 0, t.length);
}
static void triFusion(Object source[], Object destination[],
int début, int fin) {
int longueur = fin - début;
if (longueur <= 1) return;
else {
int milieu = (début + fin)/2;
triFusion(destination, source, début, milieu);
// source est trié de début à milieu
triFusion(destination, source, milieu, fin);
// source est trié de milieu à fin
// Fusion des tableaux triés dans destination
for (int i = début, p = début, q = milieu;
i < fin;
i++) {
if (q>=fin || p<milieu &&
((Comparable)source[p]).compareTo(source[q])<=0) {
destination[i] = source[p];
p++;
} else {
destination[i] = source[q];
q++;
}
}
// destination est trié de debut à fin
}
}
Tri rapide Il existe cependant un meilleur algorithme de tri (Hoare, 1962) appelé tri rapide, en anglais quicksort, qui est utilisé également par l'API Java, pour le tri des tableaux dont les éléments sont de type primitif, par les fonctions Arrays.sort(int[] t), etc. ; il diffère du tri par fusion en ce que la décomposition en deux tables est calculée, la recomposition des tables triées étant immédiate. Cette décomposition se fait par une fonction partition(), qui choisit un élément de la table, appelé pivot, réorganise la table en déplaçant tous les éléments plus petits que le pivot à la gauche du pivot et tous les éléments plus grands à sa droite, et retourne l'indice de l'élément pivot après réorganisation.
- Code:
-
static void échangerÉléments(int[] t, int m, int n) {
int temp = t[m];
t[m] = t[n];
t[n] = temp;
}
static int partition(int[] t, int m, int n) {
int v = t[m]; // valeur pivot
int i = m-1;
int j = n+1; // indice final du pivot
while (true) {
do {
j--;
} while (t[j] > v);
do {
i++;
} while (t[i] < v);
if (i<j) {
échangerÉléments(t, i, j);
} else {
return j;
}
}
}
static void triRapide(int[] t, int m, int n) {
if (m<n) {
int p = partition(t, m, n);
triRapide(t, m, p);
triRapide(t, p+1, n);
}
}
Je crois que les algos sont classés en ordre de complexité...
[EDIT]
J'ai aussi remarqué qu'avec Game maker, il était possible d'utiliser des listes d'éléments pouvant être triées...
[Extrait de l'aide]
Une liste permet de stocker une collection de valeurs dans un ordre particulier. Dans cette liste, il vous est possible d'ajouter des valeurs en fin de liste ou encore d'en insérer à un endroit quelconque de la liste. Vous adressez les valeurs de la liste via un index. De plus, vous pouvez trier les éléments de la liste, de manière ascendante ou descendante. Les listes sont utilisées dans différents cas, par exemple pour mémoriser des collections de valeurs destinées à être modifiées. Intrinséquement, elles sont implémentées sous la forme de tableaux mais, comme la gestion des listes est intégrée dans du code compilé, cela demeure beaucoup plus rapide que si vous deviez utiliser par vous-même des tableaux. Les fonctions suivantes sont à votre disposition :
ds_list_create() Crée une nouvelle liste. La fonction retourne un entier identifiant la liste qui devra ensuite être utilisé dans toutes les fonctions devant accéder à la liste créée.
ds_list_destroy(id) Détruit la liste d'ID id, libérant ainsi la mémoire utilisée. N'oubliez-pas d'appeler cette fonction lorsque vous aurez terminé d'utiliser la liste concernée.
ds_list_clear(id) Efface le contenu de la liste d'ID id, supprimant toutes les données qu'elle contient mais ne supprime pas la liste.
ds_list_size(id) Retourne le nombre de valeurs stockées dans la liste.
ds_list_empty(id) Indique si la liste est vide. Cela équivaut à tester si sa taille est à 0.
ds_list_add(id,val) Ajoute la valeur val en fin de liste d'ID id.
ds_list_insert(id,pos,val) Insére la valeur val à la position pos dans la liste d'ID id. La première valeur dans la liste se situe à la position 0, la position de la dernière valeur équivaut à la taille de la liste moins 1.
ds_list_replace(id,pos,val) Remplace la valeur à la position pos dans la liste d'ID id avec la nouvelle valeur val.
ds_list_delete(id,pos) Supprime la valeur à la position pos dans la liste d'ID id (la position 0 correspond au premier élément de la liste).
ds_list_find_index(id,val) Recherche à quelle position se trouve la valeur indiquée val dans la liste d'ID id. Si aucune valeur n'est trouvée dans la liste, la valeur -1 sera retournée.
ds_list_find_value(id,pos) Retourne la valeur mémorisée à la position indiquée pos dans la liste d'ID id.
ds_list_sort(id,ascend) Trie les valeurs de la liste. Si le paramètre ascend est positionné à true (VRAI) alors les valeurs seront triées selon l'ordre ascendant, sinon c'est l'ordre de tri descendant qui sera employé.
J'espère que cela va t'aider...
Loucheman
Accueil 
ici 
