1
00:00:00,000 --> 00:00:03,360
>> [Muziek]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Oke, dus
bubble sort is een algoritme

4
00:00:06,730 --> 00:00:08,730
u kunt gebruiken om een ​​set van elementen afstand.

5
00:00:08,730 --> 00:00:10,850
Laten we eens kijken hoe het werkt.

6
00:00:10,850 --> 00:00:13,240
>> Dus de basisidee achter
bubble sort is dit.

7
00:00:13,240 --> 00:00:17,340
We willen over het algemeen hogere bewegen
gewaardeerd elementen algemeen naar rechts

8
00:00:17,340 --> 00:00:20,340
en lager gewaardeerde elementen in het algemeen
naar links, als we zouden verwachten.

9
00:00:20,340 --> 00:00:23,256
We willen dat de lagere dingen te zijn op
het begin, en de hogere dingen

10
00:00:23,256 --> 00:00:24,970
zijn eind.

11
00:00:24,970 --> 00:00:26,130
>> Hoe doen we dat?

12
00:00:26,130 --> 00:00:28,040
Welnu, in pseudocode code,
we kunnen zeggen, laten we

13
00:00:28,040 --> 00:00:30,320
stel een ruil tegen een niet-nul waarde.

14
00:00:30,320 --> 00:00:32,570
We zullen zien waarom we dat doen in een tweede.

15
00:00:32,570 --> 00:00:36,090
En dan herhalen we de volgende
proces tot de swap teller is 0,

16
00:00:36,090 --> 00:00:39,910
of totdat wij geen swaps helemaal.

17
00:00:39,910 --> 00:00:43,170
>> Reset de swap in tegen
0 als het niet al 0.

18
00:00:43,170 --> 00:00:46,420
Kijk dan bij elke
aangrenzend paar elementen.

19
00:00:46,420 --> 00:00:49,550
Als deze twee elementen
niet in orde, swap hen,

20
00:00:49,550 --> 00:00:51,620
en voeg 1 om de swap teller.

21
00:00:51,620 --> 00:00:53,870
Als u denkt over
dit voordat je het visualiseren,

22
00:00:53,870 --> 00:00:57,471
opmerken dat deze lager zal bewegen
gewaardeerd elementen naar links

23
00:00:57,471 --> 00:01:00,720
en hoger gewaardeerde elementen naar rechts,
effectief te doen wat we willen doen,

24
00:01:00,720 --> 00:01:03,940
die bewegen die groepen
elementen op die manier.

25
00:01:03,940 --> 00:01:07,035
Laten we visualiseren hoe deze
zou kunnen kijken met behulp van ons aanbod

26
00:01:07,035 --> 00:01:10,504
die we gebruikten testen
uit deze algoritmes.

27
00:01:10,504 --> 00:01:13,420
We hebben een ongesorteerde serie hier weer,
aangeduid door alle elementen

28
00:01:13,420 --> 00:01:14,840
zijn in rood.

29
00:01:14,840 --> 00:01:17,970
En ik mijn swap teller
een nul waarde.

30
00:01:17,970 --> 00:01:20,610
Ik willekeurig gekozen
negatieve 1-- het is niet 0.

31
00:01:20,610 --> 00:01:23,840
We willen dit proces herhalen
totdat de swap teller is 0.

32
00:01:23,840 --> 00:01:26,540
Dit is de reden waarom ik mijn swap
in tegen een aantal niet-nul waarde,

33
00:01:26,540 --> 00:01:29,400
omdat anders de
swap teller zou zijn 0.

34
00:01:29,400 --> 00:01:31,610
We zouden niet eens beginnen met het
Werkwijze van het algoritme.

35
00:01:31,610 --> 00:01:33,610
Dus nogmaals, de stappen zijn--
reset de swap teller

36
00:01:33,610 --> 00:01:37,900
0, dan kijken naar elke aangrenzende
paar, en als ze buiten de orde,

37
00:01:37,900 --> 00:01:40,514
ze te verwisselen, en voeg 1
om de swap teller.

38
00:01:40,514 --> 00:01:41,680
Dus laten we beginnen met dit proces.

39
00:01:41,680 --> 00:01:44,430
Dus het eerste wat we doen is
zetten we de swap teller op 0,

40
00:01:44,430 --> 00:01:46,660
en dan beginnen we op zoek
bij elk aangrenzend paar.

41
00:01:46,660 --> 00:01:49,140
>> Dus beginnen we eerst kijken naar de 5 en 2.

42
00:01:49,140 --> 00:01:52,410
We zien dat ze uit
bestellen en zodat we ze ruilen.

43
00:01:52,410 --> 00:01:53,830
En we voegen 1 om de swap teller.

44
00:01:53,830 --> 00:01:57,860
Dus nu onze swap teller 1,
en 2 en 5 zijn ingeschakeld.

45
00:01:57,860 --> 00:01:59,370
Nu het proces herhalen we.

46
00:01:59,370 --> 00:02:03,540
>> We kijken naar de volgende aangrenzende paar,
5 en 1-- ze zijn ook buiten de orde,

47
00:02:03,540 --> 00:02:06,960
dus we ruilen hen en voeg
1 om de swap teller.

48
00:02:06,960 --> 00:02:08,900
Dan kijken we naar 5 en 3.

49
00:02:08,900 --> 00:02:13,830
Ze zijn niet in orde, dus we ruilen
hen en we voegen 1 om de swap teller.

50
00:02:13,830 --> 00:02:15,550
Dan kijken we naar 5 en 6.

51
00:02:15,550 --> 00:02:18,630
Ze zijn in orde, dus we eigenlijk niet
nodig om iets te ruilen deze tijd.

52
00:02:18,630 --> 00:02:20,250
Dan kijken we naar 6 en 4.

53
00:02:20,250 --> 00:02:24,920
Ze zijn ook buiten de orde, dus we ruilen
hen en we voegen 1 om de swap teller.

54
00:02:24,920 --> 00:02:26,230
>> Let nu op wat er gebeurd is.

55
00:02:26,230 --> 00:02:29,514
Wij hebben ons bewogen 6 helemaal tot het einde.

56
00:02:29,514 --> 00:02:32,180
Dus in selectie sorteren, als je hebt
gezien dat de video, wat we deden was

57
00:02:32,180 --> 00:02:35,290
belandden we het verplaatsen van de
kleinste elementen in de bouw

58
00:02:35,290 --> 00:02:39,640
de gesorteerde array wezen uit
van links naar rechts, klein naar groot.

59
00:02:39,640 --> 00:02:43,200
In het geval van de bubble sort, als we
volgens het desbetreffende algoritme,

60
00:02:43,200 --> 00:02:46,720
we daadwerkelijk gaan bouwen
de gesorteerde array van rechts

61
00:02:46,720 --> 00:02:49,100
naar links groot naar klein.

62
00:02:49,100 --> 00:02:53,840
We hebben effectief geborreld 6, de
grootste waarde, helemaal tot het einde.

63
00:02:53,840 --> 00:02:56,165
>> En dus kunnen we nu verklaren
dat is gesorteerd,

64
00:02:56,165 --> 00:02:59,130
en in de toekomst iterations--
gaat door de array again--

65
00:02:59,130 --> 00:03:01,280
We hoeven niet meer te overwegen 6.

66
00:03:01,280 --> 00:03:03,850
We hebben alleen te overwegen
de ongesorteerde elementen

67
00:03:03,850 --> 00:03:06,299
als we kijken naar aangrenzende paren.

68
00:03:06,299 --> 00:03:08,340
Dus we hebben een afgewerkt
passeren bubble sort.

69
00:03:08,340 --> 00:03:11,941
Dus nu gaan we terug naar de vraag,
herhalen totdat de swap teller is 0.

70
00:03:11,941 --> 00:03:13,690
Nou, de swap teller
is 4, dus we gaan

71
00:03:13,690 --> 00:03:15,410
blijven opnieuw herhalen van deze werkwijze.

72
00:03:15,410 --> 00:03:19,180
>> We gaan om de swap teller
0, en kijken naar elk aangrenzend paar.

73
00:03:19,180 --> 00:03:21,890
Dus beginnen we met 2 en 1-- ze
buiten de orde, zodat we ze ruilen

74
00:03:21,890 --> 00:03:23,620
en we voegen 1 om de swap teller.

75
00:03:23,620 --> 00:03:25,490
2 en 3, ze zijn in orde.

76
00:03:25,490 --> 00:03:27,060
We niet nodig om iets te doen.

77
00:03:27,060 --> 00:03:28,420
3 en 5 in orde zijn.

78
00:03:28,420 --> 00:03:30,150
We niet nodig om iets te doen is.

79
00:03:30,150 --> 00:03:32,515
>> 5 en 4, zijn ze uit
van de orde, en dus hebben we

80
00:03:32,515 --> 00:03:35,130
nodig hebben om ze te verwisselen en voeg
1 om de swap teller.

81
00:03:35,130 --> 00:03:38,880
En nu hebben we verhuisd 5,
de volgende grootste element,

82
00:03:38,880 --> 00:03:40,920
aan het einde van het ongesorteerde deel.

83
00:03:40,920 --> 00:03:44,360
Dus kunnen we nu noemen
deel van de gesorteerde gedeelte.

84
00:03:44,360 --> 00:03:47,180
>> Nu u op zoek bent naar de
scherm en waarschijnlijk kan vertellen,

85
00:03:47,180 --> 00:03:50,130
evenals ik, dat de matrix
is nu opgelost.

86
00:03:50,130 --> 00:03:51,820
Maar we kunnen nog niet bewijzen dat.

87
00:03:51,820 --> 00:03:54,359
We hebben geen garantie hebben
dat het is opgelost.

88
00:03:54,359 --> 00:03:56,900
Maar dit is waar de swap
toonbank gaat in het spel te komen.

89
00:03:56,900 --> 00:03:59,060
>> Dus hebben we een pas afgerond.

90
00:03:59,060 --> 00:04:00,357
De swap teller is 2.

91
00:04:00,357 --> 00:04:02,190
Dus we gaan om te herhalen
Dit proces opnieuw,

92
00:04:02,190 --> 00:04:04,290
herhalen totdat de swap teller is 0.

93
00:04:04,290 --> 00:04:05,550
Reset de swap teller op 0.

94
00:04:05,550 --> 00:04:06,820
Dus zullen we het resetten.

95
00:04:06,820 --> 00:04:09,810
>> Nu kijken naar elk aangrenzend paar.

96
00:04:09,810 --> 00:04:11,880
Dat is in orde, 1 en 2.

97
00:04:11,880 --> 00:04:13,590
2 en 3 zijn in orde.

98
00:04:13,590 --> 00:04:15,010
3 en 4 zijn in orde.

99
00:04:15,010 --> 00:04:19,250
Dus op dit punt zien we hebt voltooid
kijken naar elk aangrenzend paar,

100
00:04:19,250 --> 00:04:22,530
maar de swap teller is nog steeds 0.

101
00:04:22,530 --> 00:04:25,520
>> Als we niet over te schakelen
elke elementen, dan zijn ze

102
00:04:25,520 --> 00:04:28,340
moeten in volgorde,
hoofde van dit proces.

103
00:04:28,340 --> 00:04:32,000
En zo een efficiëntie van soorten,
dat we computer wetenschappers houden,

104
00:04:32,000 --> 00:04:35,560
is dat we nu kunnen verklaren
de hele array moet

105
00:04:35,560 --> 00:04:38,160
gesorteerd worden, omdat we niet
moet elke elementen te wisselen.

106
00:04:38,160 --> 00:04:40,380
Dat is vrij aardig.

107
00:04:40,380 --> 00:04:43,260
>> Dus wat is het ergste geval
scenario met bubble sort?

108
00:04:43,260 --> 00:04:46,240
In het ergste geval de array
volledig in omgekeerde volgorde,

109
00:04:46,240 --> 00:04:49,870
en dus moeten we elke bubble
van de grote elementen alle

110
00:04:49,870 --> 00:04:51,780
de weg over de array.

111
00:04:51,780 --> 00:04:55,350
En we effectief moeten ook
bubble alle kleine elementen back

112
00:04:55,350 --> 00:04:57,050
helemaal over de matrix, ook.

113
00:04:57,050 --> 00:05:01,950
Dus elk van de n elementen te verplaatsen
voor alle andere n elementen.

114
00:05:01,950 --> 00:05:04,102
Dus dat is het worst case scenario.

115
00:05:04,102 --> 00:05:05,810
In het beste geval
scenario echter, dit

116
00:05:05,810 --> 00:05:07,880
iets anders dan selectie sorteren.

117
00:05:07,880 --> 00:05:10,040
De array is al
naargelang als we gaan in.

118
00:05:10,040 --> 00:05:12,550
We hoeven niet te elk merk
swaps op de eerste pass.

119
00:05:12,550 --> 00:05:14,940
Dus we zouden moeten kijken
op minder elementen, toch?

120
00:05:14,940 --> 00:05:18,580
We hoeven niet te herhalen
proces meerdere malen.

121
00:05:18,580 --> 00:05:19,540
>> Dus wat betekent dat?

122
00:05:19,540 --> 00:05:22,390
Dus wat is het worst case scenario
voor de bubble sort, en wat

123
00:05:22,390 --> 00:05:25,330
het best case scenario voor bubble sort?

124
00:05:25,330 --> 00:05:27,770
Hebt u deze raden?

125
00:05:27,770 --> 00:05:32,420
In het ergste geval moet je herhalen
Bij alle n elementen n keer.

126
00:05:32,420 --> 00:05:34,220
Dus het ergste geval n kwadraat.

127
00:05:34,220 --> 00:05:36,550
>> Als de matrix perfect
gesorteerde al, alleen jij

128
00:05:36,550 --> 00:05:38,580
moeten kijken naar elk
van de elementen eenmaal.

129
00:05:38,580 --> 00:05:42,670
En als de swap teller is nog steeds 0,
je kunt zeggen dat deze array wordt gesorteerd.

130
00:05:42,670 --> 00:05:45,780
En dus in het beste geval is
eigenlijk beter dan selectie

131
00:05:45,780 --> 00:05:49,230
sort-- het omega van de n.

132
00:05:49,230 --> 00:05:50,270
>> Ik ben Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Dit is CS50.

134
00:05:52,140 --> 00:05:54,382