Tip:
Highlight text to annotate it
X
[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 Trier bulle n'est en aucun cas un algorithme de tri très efficace ou rapide.
Son pire cas d'exécution est de Big O n ²
parce que vous avez à faire n itérations à travers une liste
vérification de tous les éléments n de chaque passage, nxn = n ².
Ce moment de l'exécution signifie que le nombre d'éléments vous triez augmente,
la durée de fonctionnement augmente de façon quadratique.
>> Mais si l'efficacité n'est pas une préoccupation majeure de votre programme
ou si vous êtes seulement le tri d'un petit nombre d'éléments,
vous pourriez trouver utiles, car Trier Bubble
c'est l'un des plus simples à comprendre les algorithmes de tri
et à coder.
C'est aussi un excellent moyen de se familiariser avec la traduction d'une théorie
algorithme dans le code fonctionnement réel.
Eh bien, c'est tri à bulles pour vous. Merci d'avoir regardé.
CS50.TV