[Powered by Google Translate] [TRI BULLE] [JACKSON Steinkamp HARVARD UNIVERSITY] [C'EST CS50. CS50TV] Trier Bubble est un exemple d'un algorithme de tri - qui est une procédure de tri d'un ensemble d'éléments en ordre croissant ou décroissant. Par exemple, si vous voulez trier un tableau qui contient les numéros [3, 5, 2, 9], une mise en œuvre correcte de tri à bulles reviendrait l' tableau trié [2, 3, 5, 9] dans l'ordre croissant. Maintenant, je vais vous expliquer comment en pseudo-code de l'algorithme fonctionne. Disons que nous sommes tri d'une liste de 5 entiers - 3, 2, 9, 6 et 5. L'algorithme commence par regarder les deux premiers éléments, 3 et 2, et vérifier si elles sont hors d'usage par rapport à l'autre. Ils sont - 3 est supérieur à 2. Pour être dans l'ordre croissant, ils devraient être dans l'autre sens. Donc, nous les échanger. Maintenant, la liste ressemble à ceci: [2, 3, 9, 6, 5]. Ensuite, nous regardons les deuxième et troisième éléments, 3 et 9. Ils sont dans l'ordre correct par rapport à l'autre. C'est, 3 est inférieure à 9 sorte que l'algorithme n'a pas les échanger. Ensuite, nous cherchons à 9 et 6. Ils sont hors de vue. Donc, nous avons besoin de les changer, car 9 est supérieur à 6. Enfin, nous examinons les deux derniers nombres entiers, 9 et 5. Ils sont hors de commande, de sorte qu'ils doivent être inversées. Après le premier passage complet dans la liste, il ressemble à ceci: [2, 3, 6, 5, 9]. Pas mal. C'est presque réglé. Mais nous avons besoin de parcourir la liste de nouveau pour le faire complètement trié. Deux est inférieur à 3, donc nous n'avons pas les échanger. Trois est inférieur à 6, afin de ne pas les échanger. Six est supérieur à 5. Nous avons échangé. Six est inférieur à 9. Nous n'avons pas de swap. Après le deuxième passage, il ressemble à ceci: [2, 3, 5, 6, 9]. Parfait. Maintenant, nous allons écrire en pseudo-code. En gros, pour chaque élément de la liste, nous avons besoin de voir les choses et l'élément directement à sa droite. S'ils ne sont pas d'ordre par rapport à l'autre - qui est, si l'élément sur la gauche est supérieure à la celle de droite - il faut permuter les deux éléments. Nous faisons cela pour chaque élément de la liste, et nous avons fait un passage à travers. Maintenant nous devons juste faire les temps de passage suffisant pour assurer la liste est pleinement, correctement triés. Mais combien de fois avons-nous de passer à travers la liste de garantir que nous aurons terminé? Eh bien, dans le pire des cas, si nous avons une liste complètement à l'envers. Ensuite, il faut passer un certain nombre de traversées égal au nombre des éléments de N-1. Si cela n'a pas de sens intuitivement, pensez à un cas simple - la liste [2, 1]. Cela va prendre un pass-through pour trier correctement. [3, 2, 1] - Le pire des cas est que, avec 3 éléments triés en arrière, ça va prendre 2 itérations à trier. Après une itération, c'est [2, 1, 3]. Les rendements seconde, le tableau trié [1, 2, 3]. Donc, vous savez que vous n'aurez jamais à aller à travers le réseau, en général, plus de n-1 fois, où n est le nombre d'éléments dans le tableau. C'est ce qu'on appelle tri à bulles car les principaux éléments ont tendance à «bulle-up ' vers la droite assez rapidement. En fait, cet algorithme a un comportement très intéressant. Après m itérations à travers l'ensemble du réseau, les éléments les plus à droite sont garantis m à trier dans leur bonne place. Si vous voulez voir par vous-même, nous pouvons l'essayer sur une liste complètement à l'envers [9, 6, 5, 3, 2]. Après un passage à travers toute la liste, [Bruit d'écriture] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] l'élément le plus à droite 9 est à sa place. Après le deuxième passage, le 6 aura «buller-up» à l' deuxième place à droite. Les deux éléments à droite - 6 et 9 - seront dans leurs endroits corrects après les deux premières traversées de passe. Alors, comment pouvons-nous utiliser pour optimiser l'algorithme? Eh bien, après une itération à travers le réseau nous n'avons pas réellement besoin de vérifier l'élément le plus à droite parce que nous savons c'est réglé. Après deux itérations, nous savons que les deux éléments les plus à droite sont en place. Donc, en général, après k itérations à travers la gamme complète, vérifier les éléments k derniers est redondant puisque nous savons ils sont au bon endroit déjà. Donc, si vous triez un tableau de n éléments, sur la première itération - Vous aurez à trier l'ensemble des éléments - le premier n-0. Sur la deuxième itération, vous aurez à examiner tous les éléments sauf le dernier - le premier n-1. Une autre optimisation pourrait être de vérifier si la liste est déjà triée après chaque itération. Si elle est déjà trié, nous n'avons pas besoin de faire tout itérations plus dans la liste. Comment pouvons-nous faire cela? Eh bien, si nous ne faisons pas de swaps sur un passage de la liste, il est clair que la liste a déjà été triées parce que nous n'avons pas échanger quoi que ce soit. Donc, nous avons certainement ne pas avoir à trier à nouveau. Peut-être que vous pourriez initialiser une variable indicateur appelé «pas triés» pour false et le changer pour vrai si vous avez tous les éléments pour échanger sur une itération à travers la matrice. Ou même, faire un compteur pour compter le nombre de swaps de vous faire sur une itération donnée. A la fin d'une itération, si vous n'avez pas échanger l'un des éléments, vous connaissez la liste est déjà triée et vous avez terminé. Trier bulle, comme d'autres algorithmes de tri, peut être modifié pour fonctionner pour tous les éléments qui ont un mode de commande. C'est, compte tenu de deux éléments que vous avez un moyen de dire si le premier est supérieure, égale ou inférieure à la seconde. Par exemple, vous pouvez trier les lettres de l'alphabet en disant que a