1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [TRI BULLE]

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[C'EST CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Trier Bubble est un exemple d'un algorithme de tri -

5
00:00:11,730 --> 00:00:14,460
qui est une procédure de tri d'un ensemble d'éléments en

6
00:00:14,460 --> 00:00:15,840
ordre croissant ou décroissant.

7
00:00:15,840 --> 00:00:18,710
Par exemple, si vous voulez trier un tableau qui contient les numéros

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], une mise en œuvre correcte de tri à bulles reviendrait l'

9
00:00:23,060 --> 00:00:26,260
tableau trié [2, 3, 5, 9] dans l'ordre croissant.

10
00:00:26,260 --> 00:00:28,850
Maintenant, je vais vous expliquer comment en pseudo-code de l'algorithme fonctionne.

11
00:00:28,850 --> 00:00:34,000
>> Disons que nous sommes tri d'une liste de 5 entiers - 3, 2, 9, 6 et 5.

12
00:00:34,000 --> 00:00:37,650
L'algorithme commence par regarder les deux premiers éléments, 3 et 2,

13
00:00:37,650 --> 00:00:40,850
et vérifier si elles sont hors d'usage par rapport à l'autre.

14
00:00:40,850 --> 00:00:43,150
Ils sont - 3 est supérieur à 2.

15
00:00:43,150 --> 00:00:45,190
Pour être dans l'ordre croissant, ils devraient être dans l'autre sens.

16
00:00:45,190 --> 00:00:46,610
Donc, nous les échanger.

17
00:00:46,610 --> 00:00:49,760
Maintenant, la liste ressemble à ceci: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Ensuite, nous regardons les deuxième et troisième éléments, 3 et 9.

19
00:00:52,450 --> 00:00:55,770
Ils sont dans l'ordre correct par rapport à l'autre.

20
00:00:55,770 --> 00:00:58,800
C'est, 3 est inférieure à 9 sorte que l'algorithme n'a pas les échanger.

21
00:00:58,800 --> 00:01:01,900
Ensuite, nous cherchons à 9 et 6. Ils sont hors de vue.

22
00:01:01,900 --> 00:01:04,260
>> Donc, nous avons besoin de les changer, car 9 est supérieur à 6.

23
00:01:04,260 --> 00:01:08,840
Enfin, nous examinons les deux derniers nombres entiers, 9 et 5.

24
00:01:08,840 --> 00:01:10,850
Ils sont hors de commande, de sorte qu'ils doivent être inversées.

25
00:01:10,850 --> 00:01:13,360
Après le premier passage complet dans la liste,

26
00:01:13,360 --> 00:01:17,140
il ressemble à ceci: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Pas mal. C'est presque réglé.

28
00:01:19,690 --> 00:01:22,450
Mais nous avons besoin de parcourir la liste de nouveau pour le faire complètement trié.

29
00:01:22,450 --> 00:01:29,250
Deux est inférieur à 3, donc nous n'avons pas les échanger.

30
00:01:29,250 --> 00:01:31,700
>> Trois est inférieur à 6, afin de ne pas les échanger.

31
00:01:31,700 --> 00:01:35,500
Six est supérieur à 5. Nous avons échangé.

32
00:01:35,500 --> 00:01:38,460
Six est inférieur à 9. Nous n'avons pas de swap.

33
00:01:38,460 --> 00:01:42,170
Après le deuxième passage, il ressemble à ceci: [2, 3, 5, 6, 9]. Parfait.

34
00:01:42,170 --> 00:01:44,680
Maintenant, nous allons écrire en pseudo-code.

35
00:01:44,680 --> 00:01:48,450
En gros, pour chaque élément de la liste, nous avons besoin de voir les choses

36
00:01:48,450 --> 00:01:50,060
et l'élément directement à sa droite.

37
00:01:50,060 --> 00:01:53,420
S'ils ne sont pas d'ordre par rapport à l'autre - qui est, si l'élément sur la gauche

38
00:01:53,420 --> 00:01:56,810
est supérieure à la celle de droite - il faut permuter les deux éléments.

39
00:01:56,810 --> 00:02:01,270
>> Nous faisons cela pour chaque élément de la liste, et nous avons fait un passage à travers.

40
00:02:01,270 --> 00:02:05,160
Maintenant nous devons juste faire les temps de passage suffisant pour assurer la liste

41
00:02:05,160 --> 00:02:06,480
est pleinement, correctement triés.

42
00:02:06,480 --> 00:02:08,889
Mais combien de fois avons-nous de passer à travers la liste de

43
00:02:08,889 --> 00:02:10,400
garantir que nous aurons terminé?

44
00:02:10,400 --> 00:02:14,730
Eh bien, dans le pire des cas, si nous avons une liste complètement à l'envers.

45
00:02:14,730 --> 00:02:17,840
Ensuite, il faut passer un certain nombre de traversées égal au nombre

46
00:02:17,840 --> 00:02:19,730
des éléments de N-1.

47
00:02:19,730 --> 00:02:24,720
Si cela n'a pas de sens intuitivement, pensez à un cas simple - la liste [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Cela va prendre un pass-through pour trier correctement.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Le pire des cas est que, avec 3 éléments triés en arrière,

50
00:02:33,060 --> 00:02:34,830
ça va prendre 2 itérations à trier.

51
00:02:34,830 --> 00:02:37,980
Après une itération, c'est [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Les rendements seconde, le tableau trié [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Donc, vous savez que vous n'aurez jamais à aller à travers le réseau, en général,

54
00:02:43,350 --> 00:02:46,790
plus de n-1 fois, où n est le nombre d'éléments dans le tableau.

55
00:02:47,090 --> 00:02:50,470
C'est ce qu'on appelle tri à bulles car les principaux éléments ont tendance à «bulle-up '

56
00:02:50,470 --> 00:02:51,950
vers la droite assez rapidement.

57
00:02:51,950 --> 00:02:53,980
En fait, cet algorithme a un comportement très intéressant.

58
00:02:53,980 --> 00:02:57,410
>> Après m itérations à travers l'ensemble du réseau,

59
00:02:57,410 --> 00:02:59,000
les éléments les plus à droite sont garantis m

60
00:02:59,000 --> 00:03:01,000
à trier dans leur bonne place.

61
00:03:01,000 --> 00:03:02,280
Si vous voulez voir par vous-même,

62
00:03:02,280 --> 00:03:05,500
nous pouvons l'essayer sur une liste complètement à l'envers [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Après un passage à travers toute la liste,

64
00:03:08,220 --> 00:03:09,220
[Bruit d'écriture]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
l'élément le plus à droite 9 est à sa place.

67
00:03:21,250 --> 00:03:24,760
Après le deuxième passage, le 6 aura «buller-up» à l'

68
00:03:24,760 --> 00:03:26,220
deuxième place à droite.

69
00:03:26,220 --> 00:03:28,840
Les deux éléments à droite - 6 et 9 - seront dans leurs endroits corrects

70
00:03:28,840 --> 00:03:30,580
après les deux premières traversées de passe.

71
00:03:30,580 --> 00:03:32,590
>> Alors, comment pouvons-nous utiliser pour optimiser l'algorithme?

72
00:03:32,590 --> 00:03:34,850
Eh bien, après une itération à travers le réseau

73
00:03:34,850 --> 00:03:37,690
nous n'avons pas réellement besoin de vérifier l'élément le plus à droite

74
00:03:37,690 --> 00:03:39,200
parce que nous savons c'est réglé.

75
00:03:39,200 --> 00:03:43,050
Après deux itérations, nous savons que les deux éléments les plus à droite sont en place.

76
00:03:43,050 --> 00:03:48,260
Donc, en général, après k itérations à travers la gamme complète,

77
00:03:48,260 --> 00:03:51,550
vérifier les éléments k derniers est redondant puisque nous savons

78
00:03:51,550 --> 00:03:52,360
ils sont au bon endroit déjà.

79
00:03:52,360 --> 00:03:54,870
>> Donc, si vous triez un tableau de n éléments,

80
00:03:54,870 --> 00:03:57,870
sur la première itération - Vous aurez à trier l'ensemble des éléments - le premier n-0.

81
00:03:57,870 --> 00:04:04,170
Sur la deuxième itération, vous aurez à examiner tous les éléments sauf le dernier -

82
00:04:04,170 --> 00:04:07,090
le premier n-1.

83
00:04:07,090 --> 00:04:10,520
Une autre optimisation pourrait être de vérifier si la liste est déjà triée

84
00:04:10,520 --> 00:04:11,710
après chaque itération.

85
00:04:11,710 --> 00:04:13,900
Si elle est déjà trié, nous n'avons pas besoin de faire tout itérations plus

86
00:04:13,900 --> 00:04:15,310
dans la liste.

87
00:04:15,310 --> 00:04:16,220
Comment pouvons-nous faire cela?

88
00:04:16,220 --> 00:04:19,360
Eh bien, si nous ne faisons pas de swaps sur un passage de la liste,

89
00:04:19,360 --> 00:04:22,350
il est clair que la liste a déjà été triées parce que nous n'avons pas échanger quoi que ce soit.

90
00:04:22,350 --> 00:04:24,160
Donc, nous avons certainement ne pas avoir à trier à nouveau.

91
00:04:24,160 --> 00:04:27,960
>> Peut-être que vous pourriez initialiser une variable indicateur appelé «pas triés» pour

92
00:04:27,960 --> 00:04:30,990
false et le changer pour vrai si vous avez tous les éléments pour échanger sur

93
00:04:30,990 --> 00:04:32,290
une itération à travers la matrice.

94
00:04:32,290 --> 00:04:35,350
Ou même, faire un compteur pour compter le nombre de swaps de vous faire

95
00:04:35,350 --> 00:04:37,040
sur une itération donnée.

96
00:04:37,040 --> 00:04:40,040
A la fin d'une itération, si vous n'avez pas échanger l'un des éléments,

97
00:04:40,040 --> 00:04:41,780
vous connaissez la liste est déjà triée et vous avez terminé.

98
00:04:41,780 --> 00:04:44,090
Trier bulle, comme d'autres algorithmes de tri, peut être

99
00:04:44,090 --> 00:04:46,960
modifié pour fonctionner pour tous les éléments qui ont un mode de commande.

100
00:04:46,960 --> 00:04:50,610
>> C'est, compte tenu de deux éléments que vous avez un moyen de dire si le premier

101
00:04:50,610 --> 00:04:53,770
est supérieure, égale ou inférieure à la seconde.

102
00:04:53,770 --> 00:04:56,870
Par exemple, vous pouvez trier les lettres de l'alphabet en disant

103
00:04:56,870 --> 00:05:00,520
que a <b, b <c, etc

104
00:05:00,520 --> 00:05:03,830
Ou vous pouvez trier les jours de la semaine où le dimanche est moins que lundi

105
00:05:03,830 --> 00:05:05,110
qui est inférieure à mardi.

106
00:05:05,110 --> 00:05:09,630
>> Trier bulle n'est en aucun cas un algorithme de tri très efficace ou rapide.

107
00:05:09,630 --> 00:05:12,370
Son pire cas d'exécution est de Big O n ²

108
00:05:12,370 --> 00:05:14,810
parce que vous avez à faire n itérations à travers une liste

109
00:05:14,810 --> 00:05:18,430
vérification de tous les éléments n de chaque passage, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Ce moment de l'exécution signifie que le nombre d'éléments vous triez augmente,

111
00:05:22,730 --> 00:05:24,330
la durée de fonctionnement augmente de façon quadratique.

112
00:05:24,330 --> 00:05:27,330
>> Mais si l'efficacité n'est pas une préoccupation majeure de votre programme

113
00:05:27,330 --> 00:05:29,550
ou si vous êtes seulement le tri d'un petit nombre d'éléments,

114
00:05:29,550 --> 00:05:31,660
vous pourriez trouver utiles, car Trier Bubble

115
00:05:31,660 --> 00:05:33,360
c'est l'un des plus simples à comprendre les algorithmes de tri

116
00:05:33,360 --> 00:05:34,250
et à coder.

117
00:05:34,250 --> 00:05:37,270
C'est aussi un excellent moyen de se familiariser avec la traduction d'une théorie

118
00:05:37,270 --> 00:05:40,220
algorithme dans le code fonctionnement réel.

119
00:05:40,220 --> 00:05:43,000
Eh bien, c'est tri à bulles pour vous. Merci d'avoir regardé.

120
00:05:43,000 --> 00:05:44,000
CS50.TV