1
00:00:00,000 --> 00:00:03,360
>> [MUSIC SPILLE]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Greit, så
boble liksom er en algoritme

4
00:00:06,730 --> 00:00:08,730
du kan bruke til å sortere et sett av elementer.

5
00:00:08,730 --> 00:00:10,850
La oss ta en titt på hvordan det fungerer.

6
00:00:10,850 --> 00:00:13,240
>> Så den grunnleggende ideen bak
boble liksom er dette.

7
00:00:13,240 --> 00:00:17,340
Vi vanligvis ønsker å flytte høyere
verdsatte elementer vanligvis til høyre,

8
00:00:17,340 --> 00:00:20,340
og lavere verdsatte elementer generelt
til venstre, som vi forventer.

9
00:00:20,340 --> 00:00:23,256
Vi ønsker de lavere ting å være på
begynnelsen, og de høyere ting

10
00:00:23,256 --> 00:00:24,970
å være på slutten.

11
00:00:24,970 --> 00:00:26,130
>> Hvordan gjør vi dette?

12
00:00:26,130 --> 00:00:28,040
Vel i pseudokode,
vi kunne si, la oss

13
00:00:28,040 --> 00:00:30,320
satt en swap disken til en annen verdi enn null.

14
00:00:30,320 --> 00:00:32,570
Vi vil se hvorfor vi gjør det i et sekund.

15
00:00:32,570 --> 00:00:36,090
Og da vi gjenta følgende
prosessen til swap telleren er 0,

16
00:00:36,090 --> 00:00:39,910
eller før vi gjør ingen bytteavtaler i det hele tatt.

17
00:00:39,910 --> 00:00:43,170
>> Tilbakestill swap telleren til
0 hvis det ikke allerede er 0.

18
00:00:43,170 --> 00:00:46,420
Deretter se på hver
tilstøtende par av elementer.

19
00:00:46,420 --> 00:00:49,550
Hvis disse to elementene er
ikke i orden, bytte dem,

20
00:00:49,550 --> 00:00:51,620
og legge en til swap disken.

21
00:00:51,620 --> 00:00:53,870
Hvis du tenker på
dette før du visualisere det,

22
00:00:53,870 --> 00:00:57,471
Legg merke til at dette vil gå lavere
verdsatte elementer til venstre

23
00:00:57,471 --> 00:01:00,720
og høyere verdsatt elementer til høyre,
effektivt å gjøre det vi ønsker å gjøre,

24
00:01:00,720 --> 00:01:03,940
som er flytte disse gruppene
av elementer i den måten.

25
00:01:03,940 --> 00:01:07,035
La oss visualisere hvordan dette
kan se ved hjelp av vårt utvalg

26
00:01:07,035 --> 00:01:10,504
som vi brukte for å teste
ut disse algoritmene.

27
00:01:10,504 --> 00:01:13,420
Vi har en usortert utvalg her igjen,
angitt ved alle elementene

28
00:01:13,420 --> 00:01:14,840
være i rødt.

29
00:01:14,840 --> 00:01:17,970
Og jeg satte min swap disk
til en annen verdi enn null.

30
00:01:17,970 --> 00:01:20,610
Jeg valgte vilkårlig
negative 1-- det er ikke 0.

31
00:01:20,610 --> 00:01:23,840
Vi ønsker å gjenta denne prosessen
til swap telleren er 0.

32
00:01:23,840 --> 00:01:26,540
Det er derfor jeg satt min swap
telleren til en verdi forskjellig fra null,

33
00:01:26,540 --> 00:01:29,400
fordi ellers
swap disken ville være 0.

34
00:01:29,400 --> 00:01:31,610
Vi ville ikke engang begynne
Fremgangsmåten ifølge algoritmen.

35
00:01:31,610 --> 00:01:33,610
Så igjen, trinnene are--
nullstille swap disken

36
00:01:33,610 --> 00:01:37,900
til 0, og deretter se på hver tilstøtende
pair, og hvis de er ute av drift,

37
00:01:37,900 --> 00:01:40,514
bytte dem, og tilsett 1
til swap disken.

38
00:01:40,514 --> 00:01:41,680
Så la oss starte denne prosessen.

39
00:01:41,680 --> 00:01:44,430
Så det første vi gjør er
vi sette swap disken til 0,

40
00:01:44,430 --> 00:01:46,660
og da vi begynne å se
ved hvert tilstøtende par.

41
00:01:46,660 --> 00:01:49,140
>> Så vi først begynner å se på 5 og 2.

42
00:01:49,140 --> 00:01:52,410
Vi ser at de er ute av
bestille og så vi bytte dem.

43
00:01:52,410 --> 00:01:53,830
Og vi legger en til swap disken.

44
00:01:53,830 --> 00:01:57,860
Så nå vår swap disken er 1,
og 2 og 5 har blitt slått.

45
00:01:57,860 --> 00:01:59,370
Nå gjentar vi prosessen på nytt.

46
00:01:59,370 --> 00:02:03,540
>> Vi ser på den neste tilstøtende par,
5 og 1-- de er også ute av drift,

47
00:02:03,540 --> 00:02:06,960
så vi bytte dem og legge
En til swap disken.

48
00:02:06,960 --> 00:02:08,900
Så ser vi på fem og tre.

49
00:02:08,900 --> 00:02:13,830
De er ute av drift, så vi bytte
dem, og vi legger en til swap disken.

50
00:02:13,830 --> 00:02:15,550
Så ser vi på fem og seks.

51
00:02:15,550 --> 00:02:18,630
De er i orden, slik at vi ikke faktisk
trenger å bytte noe denne gangen.

52
00:02:18,630 --> 00:02:20,250
Så ser vi på 6 og 4.

53
00:02:20,250 --> 00:02:24,920
De er også ute av drift, så vi bytte
dem, og vi legger en til swap disken.

54
00:02:24,920 --> 00:02:26,230
>> Nå legge merke til hva som har skjedd.

55
00:02:26,230 --> 00:02:29,514
Vi har flyttet 6 hele veien til enden.

56
00:02:29,514 --> 00:02:32,180
Så i utvalget slag, hvis du har
sett at video, det vi gjorde var

57
00:02:32,180 --> 00:02:35,290
vi endte opp med å flytte den
minste elementene i bygningen

58
00:02:35,290 --> 00:02:39,640
den sorterte rekke hovedsak fra
venstre til høyre, minst til størst.

59
00:02:39,640 --> 00:02:43,200
I tilfelle av boblen slag, hvis vi
Følgende denne algoritmen,

60
00:02:43,200 --> 00:02:46,720
vi faktisk kommer til å være å bygge
den sorterte rekke fra høyre

61
00:02:46,720 --> 00:02:49,100
til venstre, størst til minst.

62
00:02:49,100 --> 00:02:53,840
Vi har effektivt boblet 6,
største verdi, helt til enden.

63
00:02:53,840 --> 00:02:56,165
>> Og så kan vi nå erklære
at det er sortert,

64
00:02:56,165 --> 00:02:59,130
og i fremtiden iterations--
går gjennom rekke igjen--

65
00:02:59,130 --> 00:03:01,280
vi trenger ikke å vurdere seks lenger.

66
00:03:01,280 --> 00:03:03,850
Vi trenger bare å vurdere
de usorterte elementer

67
00:03:03,850 --> 00:03:06,299
når vi ser på tilstøtende par.

68
00:03:06,299 --> 00:03:08,340
Så vi er ferdig med én
passere gjennom boble slag.

69
00:03:08,340 --> 00:03:11,941
Så nå går vi tilbake til spørsmålet,
gjenta til swap telleren er 0.

70
00:03:11,941 --> 00:03:13,690
Vel swap disken
er fire, så vi kommer

71
00:03:13,690 --> 00:03:15,410
for å holde gjenta denne prosessen på nytt.

72
00:03:15,410 --> 00:03:19,180
>> Vi kommer til å nullstille swap disken
til 0, og se på hvert tilstøtende par.

73
00:03:19,180 --> 00:03:21,890
Så vi starter med to og 1-- de er
ute av drift, så vi bytte dem

74
00:03:21,890 --> 00:03:23,620
og vi legger en til swap disken.

75
00:03:23,620 --> 00:03:25,490
2 og 3, de er i orden.

76
00:03:25,490 --> 00:03:27,060
Vi trenger ikke å gjøre noe.

77
00:03:27,060 --> 00:03:28,420
3 og 5 er i orden.

78
00:03:28,420 --> 00:03:30,150
Vi trenger ikke å gjøre noe der.

79
00:03:30,150 --> 00:03:32,515
>> 5 og 4, de er ute
av orden, og så vi

80
00:03:32,515 --> 00:03:35,130
trenger å bytte dem og legge
En til swap disken.

81
00:03:35,130 --> 00:03:38,880
Og nå har vi flyttet 5,
den nest største element,

82
00:03:38,880 --> 00:03:40,920
til enden av usortert partiet.

83
00:03:40,920 --> 00:03:44,360
Så vi kan nå kalle det
en del av den sorterte partiet.

84
00:03:44,360 --> 00:03:47,180
>> Nå du ser på
skjermen og sannsynligvis kan fortelle,

85
00:03:47,180 --> 00:03:50,130
som kan jeg, at matrisen
er sortert akkurat nå.

86
00:03:50,130 --> 00:03:51,820
Men vi kan ikke bevise det ennå.

87
00:03:51,820 --> 00:03:54,359
Vi har ikke en garanti
at det er sortert.

88
00:03:54,359 --> 00:03:56,900
Men det er her swap
disken kommer til å komme inn i bildet.

89
00:03:56,900 --> 00:03:59,060
>> Så vi har fullført et pass.

90
00:03:59,060 --> 00:04:00,357
Swap telleren er 2.

91
00:04:00,357 --> 00:04:02,190
Så vi kommer til å gjenta
denne prosessen på nytt,

92
00:04:02,190 --> 00:04:04,290
gjenta til swap telleren er 0.

93
00:04:04,290 --> 00:04:05,550
Tilbakestill swap disken til 0.

94
00:04:05,550 --> 00:04:06,820
Så vi vil tilbakestille det.

95
00:04:06,820 --> 00:04:09,810
>> Nå ser på hvert tilstøtende par.

96
00:04:09,810 --> 00:04:11,880
Det er i orden, 1 og 2.

97
00:04:11,880 --> 00:04:13,590
2 og 3 er i orden.

98
00:04:13,590 --> 00:04:15,010
3 og 4 er i orden.

99
00:04:15,010 --> 00:04:19,250
Så på dette punktet, merker vi har fullført
ser på hvert nabopar,

100
00:04:19,250 --> 00:04:22,530
men swap disken er fortsatt 0.

101
00:04:22,530 --> 00:04:25,520
>> Hvis vi ikke trenger å bytte
noen elementer, da de

102
00:04:25,520 --> 00:04:28,340
må være i orden, etter
I kraft av denne fremgangsmåten.

103
00:04:28,340 --> 00:04:32,000
Og så en effektivitet av former,
At vi dataforskere elsker,

104
00:04:32,000 --> 00:04:35,560
er vi nå kan erklære
hele matrisen må

105
00:04:35,560 --> 00:04:38,160
sorteres, fordi vi ikke
må bytte noen elementer.

106
00:04:38,160 --> 00:04:40,380
Det er ganske fin.

107
00:04:40,380 --> 00:04:43,260
>> Så hva er det verste tilfellet
scenario med boble liksom?

108
00:04:43,260 --> 00:04:46,240
I verste fall er matrisen
i helt motsatt rekkefølge,

109
00:04:46,240 --> 00:04:49,870
og så har vi å boble hver
av de store elementer alle

110
00:04:49,870 --> 00:04:51,780
veien over rekken.

111
00:04:51,780 --> 00:04:55,350
Og vi effektivt må også
boble alle de små elementer iden

112
00:04:55,350 --> 00:04:57,050
hele veien over rekken, også.

113
00:04:57,050 --> 00:05:01,950
Slik at hver av de n elementene har til å bevege seg
på tvers av alle de andre n elementene.

114
00:05:01,950 --> 00:05:04,102
Så det er worst case scenario.

115
00:05:04,102 --> 00:05:05,810
I beste fall
scenario skjønt, er dette

116
00:05:05,810 --> 00:05:07,880
litt forskjellig fra utvalget slag.

117
00:05:07,880 --> 00:05:10,040
Matrisen er allerede
sortert når vi går i.

118
00:05:10,040 --> 00:05:12,550
Vi trenger ikke å gjøre noen
swaps på første pass.

119
00:05:12,550 --> 00:05:14,940
Så vi må kanskje se
på færre elementer, ikke sant?

120
00:05:14,940 --> 00:05:18,580
Vi trenger ikke å gjenta denne
behandle en rekke ganger over.

121
00:05:18,580 --> 00:05:19,540
>> Så hva betyr det?

122
00:05:19,540 --> 00:05:22,390
Så hva er worst case scenario
for boble sortere, og hva som er

123
00:05:22,390 --> 00:05:25,330
best case scenario for boble liksom?

124
00:05:25,330 --> 00:05:27,770
Visste du antar dette?

125
00:05:27,770 --> 00:05:32,420
I verste fall må du reagere
på tvers av alle de n elementene n ganger.

126
00:05:32,420 --> 00:05:34,220
Så det verste tilfellet er n squared.

127
00:05:34,220 --> 00:05:36,550
>> Hvis rekken er helt
sortert skjønt, bare du

128
00:05:36,550 --> 00:05:38,580
må se på hver
av elementene gang.

129
00:05:38,580 --> 00:05:42,670
Og hvis swap disken er fortsatt 0,
du kan si denne tabellen er sortert.

130
00:05:42,670 --> 00:05:45,780
Og så i beste fall, er dette
faktisk bedre enn utvalg

131
00:05:45,780 --> 00:05:49,230
sort-- det er omega n.

132
00:05:49,230 --> 00:05:50,270
>> Jeg er Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Dette er CS50.

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