Share
Dans ce petit conseil, je vais vous montrer comment et pourquoi l’algorithme de tri à bulles fonctionne et comment le mettre en œuvre dans AS3. Vous allez vous retrouver avec une classe que vous pouvez utiliser dans n'importe quel projet Flash, pour trier n'importe quel tableau.
Voici une simple démonstration du résultat de l'algorithme de tri à bulle:
Bien sûr, ce SWF ne prouve pas grand chose par lui-même! Prenez les fichiers source et vous pouvez éditer vous-même le tableau d'entrée.
Comme cet algorithme sera utilisé plus d'une fois, c'est une bonne idée de créer une classe pour cela, afin de pouvoir l'utiliser facilement dans n'importe quel projet AS3:
Configurer un projet Flash de base et créer un fichier dans le dossier du projet BubbleSort.as. (Nous allons créer un fichier de test ici aussi, afin de pouvoir le tester.)
Si vous ne savez pas comment utiliser les classes, consultez ce didacticiel: Comment utiliser une classe de document dans Flash.
Nous n'aurons pas besoin du constructeur, alors débarrassez-vous-en! Votre classe devrait ressembler à ceci:
package public class BubbleSort
Cet algorithme n'est pas la méthode la plus rapide ni la plus efficace pour trier une série de nombres, mais c'est la plus facile à comprendre..
Cette image le résume; à chaque étape, chaque paire de nombres est comparée, en partant de la fin, et échangée (au moyen d’un "disque de secours"). temp variable) si elles sont dans le mauvais ordre.
Une fois que toutes les paires consécutives ont été vérifiées, cela garantit que le nombre au début est le plus grand nombre de la séquence; on répète ensuite, vérifiant chaque paire de nombres en dehors du nombre au début. Une fois que toutes les paires consécutives ont été vérifiées, nous savons que le premier deux les nombres dans la séquence sont dans le bon ordre (ils sont le plus grand et le deuxième plus grand). Nous continuons jusqu'à ce que nous ayons mis chaque numéro dans le bon ordre.
C'est ce qu'on appelle le "type de bulle" car, à chaque passage dans le tableau, le plus grand nombre "flotte" vers le haut du tableau, comme une bulle dans l'eau..
Permet de commencer à écrire le code. Nous appellerons la fonction principale bsort ():
Accentsconagua
package public class BubbleSort fonction publique bsort (arr: Array, sortType: String): Array var temp: String; if (sortType.toLocaleLowerCase () == "décroissant") else if (sortType.toLocaleLowerCase () == "ascending") sinon lance une nouvelle erreur ("Vous avez une faute de frappe lorsque vous appelez la fonction bsort (), utilisez 'croissant' ou 'décroissant' pour sortType! "); retour arr; La fonction obtient deux paramètres. Le premier paramètre, arr, sera le tableau à trier; le deuxième paramètre, sortType sera utilisé pour décider si l'utilisateur veut que le tableau soit trié par ordre croissant ou décroissant.
Dans la fonction, nous déclarons un temp variable qui contiendra les éléments du tableau au cas où nous aurions besoin d’échanger les deux éléments. Vous pouvez vous demander pourquoi ce n'est pas un nombre. C'est parce que notre classe sera capable de gérer les tableaux de chaînes aussi, en les triant par ordre alphabétique; nous pouvons convertir des nombres en chaînes et inversement, mais nous ne pouvons pas convertir des chaînes en nombres et inversement, nous utilisons donc une chaîne pour cette variable, juste pour être sûr.
Nous utilisons un si-autre bloquer pour diviser notre code en deux branches, en fonction de la direction dans laquelle l'utilisateur souhaite trier. (Si l'utilisateur ne fournit pas un choix valide, le programme déclenche une erreur.)
La différence entre le code de chaque branche sera un seul caractère: soit < ou >.
Écrivons l'algorithme. Nous commençons par la partie descendante:
package public class BubbleSort fonction publique bsort (arr: Array, sortType: String): Array var temp: String; if (sortType.toLocaleLowerCase () == "décroissant") pour (var i: uint = 0; i < arr.length; i++) for(var j:uint=arr.length-1; j > je; j--) else if (sortType.toLocaleLowerCase () == "croissant") sinon lance une nouvelle erreur ("Vous avez une faute de frappe lorsque vous appelez la fonction bsort (), veuillez utiliser 'croissant' ou 'décroissant 'pour sortType! "); retour arr; Comme vous pouvez le voir, nous utilisons imbriqué pour boucles. On va du premier élément au dernier élément du tableau; l'autre recule.
Inspectons l'intérieur "j"boucle d'abord. Comme le montre le diagramme précédent, commençons par comparer les deux derniers éléments du tableau, qui sont arr [j-1] et arr [j] (dans la première itération). Si arr [j-1] est inférieur à arr [j] ils doivent être échangés.
Dans les deux cas, on soustrait un de j (à travers le "j--"call in line 131), qui change quelle paire de numéros sera comparée à la prochaine boucle.
j commence à une valeur de arr.length-1, et se termine par une valeur de 1, ce qui signifie que l'intérieur pour boucle vérifie chaque paire consécutive, en commençant par la dernière paire (où j équivaut à arr.length-1) et se terminant par la première paire (où j équivaut à 1).
Maintenant regardons l'extérieur "je"boucle. Une fois que toutes les paires ont été vérifiées et permutées si nécessaire, je est augmenté (par le "je++"call in line 129). Cela signifie que la prochaine fois, j va commencer à arr.length-1 encore, mais se terminent à 2 this time - signifiant que la première paire de la séquence ne sera ni vérifiée ni échangée. C’est exactement ce que nous voulons, puisque nous savons que le premier numéro est dans la bonne position.
Au fur et à mesure, il ne restera finalement que deux éléments à vérifier dans la boucle interne. Une fois qu'ils ont terminé, nous savons que nous avons trié le tableau.!
Voici à quoi cela ressemble dans le code:
