1
00:00:00,000 --> 00:00:03,360
>> [Speel van musiek]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Alle reg, sodat
borrel soort is 'n algoritme

4
00:00:06,730 --> 00:00:08,730
jy kan gebruik om 'n stel van elemente te sorteer.

5
00:00:08,730 --> 00:00:10,850
Kom ons neem 'n blik op hoe dit werk.

6
00:00:10,850 --> 00:00:13,240
>> So het die basiese idee agter
borrel soort is dit.

7
00:00:13,240 --> 00:00:17,340
Ons wil die algemeen hoër beweeg
gewaardeer elemente algemeen na regs,

8
00:00:17,340 --> 00:00:20,340
en laer gewaardeer elemente algemeen
aan die linkerkant, soos ons sou verwag.

9
00:00:20,340 --> 00:00:23,256
Ons wil hê die laer dinge te wees by
die begin en die hoër dinge

10
00:00:23,256 --> 00:00:24,970
te wees aan die einde.

11
00:00:24,970 --> 00:00:26,130
>> Hoe kan ons dit doen?

12
00:00:26,130 --> 00:00:28,040
Wel, in pseudokode kode,
ons kon sê, laat

13
00:00:28,040 --> 00:00:30,320
stel 'n ruil toonbank om 'n nie-nul waarde.

14
00:00:30,320 --> 00:00:32,570
Ons sal sien waarom ons dit doen in 'n tweede.

15
00:00:32,570 --> 00:00:36,090
En dan herhaal ons die volgende
proses totdat die swap toonbank is 0,

16
00:00:36,090 --> 00:00:39,910
of totdat ons nie swaps at all.

17
00:00:39,910 --> 00:00:43,170
>> Herstel die swap toonbank
0 as dit nie reeds 0.

18
00:00:43,170 --> 00:00:46,420
Kyk dan by elke
aangrensende denim elemente.

19
00:00:46,420 --> 00:00:49,550
As daardie twee elemente is
nie in orde is, ruil hulle

20
00:00:49,550 --> 00:00:51,620
en voeg 1 tot die omruil toonbank.

21
00:00:51,620 --> 00:00:53,870
As jy dink oor
dit voordat jy dit visualiseer,

22
00:00:53,870 --> 00:00:57,471
sien dat hierdie laer sal beweeg
gewaardeer elemente aan die linkerkant

23
00:00:57,471 --> 00:01:00,720
en hoër gewaardeer elemente na regs,
effektief te doen wat ons wil doen,

24
00:01:00,720 --> 00:01:03,940
wat is die groepe beweeg
elemente in die manier.

25
00:01:03,940 --> 00:01:07,035
Kom ons visualiseer hoe dit
kan lyk met behulp van ons verskeidenheid

26
00:01:07,035 --> 00:01:10,504
wat ons gebruik om te toets
uit hierdie algoritmes.

27
00:01:10,504 --> 00:01:13,420
Ons het 'n verskeidenheid ongesorteerde weer hier,
aangedui deur al die elemente

28
00:01:13,420 --> 00:01:14,840
om in rooi.

29
00:01:14,840 --> 00:01:17,970
En ek het my ruil counter
om 'n nie-nul waarde.

30
00:01:17,970 --> 00:01:20,610
Ek arbitrêr gekies
negatiewe 1-- dit is nie 0.

31
00:01:20,610 --> 00:01:23,840
Ons wil hierdie proses herhaal
totdat die swap toonbank is 0.

32
00:01:23,840 --> 00:01:26,540
Dit is waarom ek my ruil
counter sommige nie-nul waarde,

33
00:01:26,540 --> 00:01:29,400
want anders sal die
swap toonbank sou wees 0.

34
00:01:29,400 --> 00:01:31,610
Ons wil nie eens begin om die
proses van die algoritme.

35
00:01:31,610 --> 00:01:33,610
So weer, die stappe are--
weer die toonbank ruil

36
00:01:33,610 --> 00:01:37,900
0, dan kyk na elke aangrensende
paar, en as hulle buite orde,

37
00:01:37,900 --> 00:01:40,514
ruil, en voeg 1
om die ruiltransaksie toonbank.

38
00:01:40,514 --> 00:01:41,680
So laat ons begin hierdie proses.

39
00:01:41,680 --> 00:01:44,430
So die eerste ding wat ons doen, is
Ons stel die swap teen 0,

40
00:01:44,430 --> 00:01:46,660
en dan begin ons soek
by elke aangrensende paar.

41
00:01:46,660 --> 00:01:49,140
>> So begin ons eerste kyk na 5 en 2.

42
00:01:49,140 --> 00:01:52,410
Ons sien dat hulle uit
bestel en sodat ons hulle ruil.

43
00:01:52,410 --> 00:01:53,830
En ons voeg 1 tot die omruil toonbank.

44
00:01:53,830 --> 00:01:57,860
So nou is ons swap toonbank is 1,
en 2 en 5 is aangeskakel.

45
00:01:57,860 --> 00:01:59,370
Nou is die proses herhaal ons.

46
00:01:59,370 --> 00:02:03,540
>> Ons kyk na die volgende aangrensende paar,
5 en 1-- dit is ook buite werking is,

47
00:02:03,540 --> 00:02:06,960
sodat ons ruil hulle en voeg
1 by die ruil toonbank.

48
00:02:06,960 --> 00:02:08,900
Dan kyk ons ​​na 5 en 3.

49
00:02:08,900 --> 00:02:13,830
Hulle is buite orde, so ons ruil
hulle en ons voeg 1 tot die omruil toonbank.

50
00:02:13,830 --> 00:02:15,550
Dan kyk ons ​​na 5 en 6.

51
00:02:15,550 --> 00:02:18,630
Hulle is in orde, so ons doen nie eintlik
nodig om iets te ruil hierdie tyd.

52
00:02:18,630 --> 00:02:20,250
Dan kyk ons ​​na 6 en 4.

53
00:02:20,250 --> 00:02:24,920
Hulle is ook buite werking is, sodat ons ruil
hulle en ons voeg 1 tot die omruil toonbank.

54
00:02:24,920 --> 00:02:26,230
>> Nou sien wat gebeur het.

55
00:02:26,230 --> 00:02:29,514
Ons het verhuis 6 al die pad tot die einde.

56
00:02:29,514 --> 00:02:32,180
So in seleksie soort, as jy het
gesien dat die video, wat ons gedoen het, was

57
00:02:32,180 --> 00:02:35,290
ons beland die verskuiwing van die
kleinste elemente in die bou

58
00:02:35,290 --> 00:02:39,640
die gesorteerde skikking wese van
links na regs, die kleinste tot die grootste.

59
00:02:39,640 --> 00:02:43,200
In die geval van die borrel soort, as ons
volgende hierdie spesifieke algoritme,

60
00:02:43,200 --> 00:02:46,720
ons is eintlik gaan bou
die gesorteerde skikking van regs

61
00:02:46,720 --> 00:02:49,100
na links, die grootste tot die kleinste.

62
00:02:49,100 --> 00:02:53,840
Ons het effektief geborrel 6, die
grootste waarde, al die pad tot die einde.

63
00:02:53,840 --> 00:02:56,165
>> En so kan ons nou verklaar
dat is gesorteer,

64
00:02:56,165 --> 00:02:59,130
en in die toekoms iterations--
gaan deur die skikking again--

65
00:02:59,130 --> 00:03:01,280
ons nie meer hoef te oorweeg 6.

66
00:03:01,280 --> 00:03:03,850
Ons het net om te oorweeg
die ongesorteerde elemente

67
00:03:03,850 --> 00:03:06,299
wanneer ons kyk na die aangrensende pare.

68
00:03:06,299 --> 00:03:08,340
So het ons een klaar
deur borrelsortering.

69
00:03:08,340 --> 00:03:11,941
So nou gaan ons terug na die vraag,
herhaal totdat die swap toonbank is 0.

70
00:03:11,941 --> 00:03:13,690
Wel, die ruil counter
is 4, so ons gaan

71
00:03:13,690 --> 00:03:15,410
hou weer herhaal hierdie proses.

72
00:03:15,410 --> 00:03:19,180
>> Ons gaan na die toonbank ruil herstel
0, en kyk na elke aangrensende paar.

73
00:03:19,180 --> 00:03:21,890
So het ons begin met 2 en 1-- hulle is
buite werking is, sodat ons hulle ruil

74
00:03:21,890 --> 00:03:23,620
en ons voeg 1 tot die omruil toonbank.

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

76
00:03:25,490 --> 00:03:27,060
Ons het nie nodig om iets te doen.

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

78
00:03:28,420 --> 00:03:30,150
Ons het nie nodig om iets daar te doen.

79
00:03:30,150 --> 00:03:32,515
>> 5 en 4, is hulle uit
van orde, en so het ons

80
00:03:32,515 --> 00:03:35,130
nodig het om hulle te ruil en voeg
1 by die ruil toonbank.

81
00:03:35,130 --> 00:03:38,880
En nou het ons verhuis 5,
die volgende grootste element,

82
00:03:38,880 --> 00:03:40,920
tot aan die einde van die ongesorteerde gedeelte.

83
00:03:40,920 --> 00:03:44,360
So kan ons nou noem
deel van die gesorteer gedeelte.

84
00:03:44,360 --> 00:03:47,180
>> Nou jy kyk na die
skerm en waarskynlik kan sê,

85
00:03:47,180 --> 00:03:50,130
as ek kan, wat die skikking
is nou gesorteer.

86
00:03:50,130 --> 00:03:51,820
Maar ons kan nog nie bewys dat.

87
00:03:51,820 --> 00:03:54,359
Ons het nie 'n waarborg het
dat dit gesorteer.

88
00:03:54,359 --> 00:03:56,900
Maar dit is waar die ruil
counter gaan in die spel kom.

89
00:03:56,900 --> 00:03:59,060
>> So het ons 'n pass voltooi.

90
00:03:59,060 --> 00:04:00,357
Die swap toonbank is 2.

91
00:04:00,357 --> 00:04:02,190
So ons gaan herhaal
hierdie proses weer

92
00:04:02,190 --> 00:04:04,290
herhaal totdat die swap toonbank is 0.

93
00:04:04,290 --> 00:04:05,550
Herstel die swap toonbank 0.

94
00:04:05,550 --> 00:04:06,820
So sal ons dit weer.

95
00:04:06,820 --> 00:04:09,810
>> Nou kyk na elke aangrensende paar.

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

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

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

99
00:04:15,010 --> 00:04:19,250
So op hierdie punt, sien ons voltooi het
soek op elke aangrensende paar,

100
00:04:19,250 --> 00:04:22,530
maar die swap toonbank is nog 0.

101
00:04:22,530 --> 00:04:25,520
>> As ons nie hoef te skakel
enige elemente, dan sal hulle

102
00:04:25,520 --> 00:04:28,340
moet wees om deur
hoofde van hierdie proses.

103
00:04:28,340 --> 00:04:32,000
En so 'n doeltreffendheid van spesies,
dat ons rekenaar wetenskaplikes liefhet,

104
00:04:32,000 --> 00:04:35,560
is ons nou kan verklaar
die hele skikking moet

105
00:04:35,560 --> 00:04:38,160
gesorteer, want ons het nie
het om enige elemente te ruil.

106
00:04:38,160 --> 00:04:40,380
Dit is redelik nice.

107
00:04:40,380 --> 00:04:43,260
>> So, wat is die ergste geval
scenario met borrelsortering?

108
00:04:43,260 --> 00:04:46,240
In die ergste geval die skikking is
in totaal omgekeerde volgorde,

109
00:04:46,240 --> 00:04:49,870
en so het ons na elke borrel
van die groot elemente al

110
00:04:49,870 --> 00:04:51,780
die pad oor die skikking.

111
00:04:51,780 --> 00:04:55,350
En ons moet ook effektief
borrel al die klein elemente terug

112
00:04:55,350 --> 00:04:57,050
al die pad oor die skikking, ook.

113
00:04:57,050 --> 00:05:01,950
So elkeen van die N elemente het om te beweeg
oor al die ander elemente N.

114
00:05:01,950 --> 00:05:04,102
So wat is die ergste geval scenario.

115
00:05:04,102 --> 00:05:05,810
In die beste geval
scenario al is, dit is

116
00:05:05,810 --> 00:05:07,880
effens anders seleksie soort.

117
00:05:07,880 --> 00:05:10,040
Die skikking is reeds
gesorteer wanneer ons gaan in.

118
00:05:10,040 --> 00:05:12,550
Ons het nie nodig om enige te maak
swaps op die eerste pass.

119
00:05:12,550 --> 00:05:14,940
Sodat ons kan om te kyk
op minder elemente, reg?

120
00:05:14,940 --> 00:05:18,580
Ons hoef nie te herhaal hierdie
verwerk 'n paar keer oor.

121
00:05:18,580 --> 00:05:19,540
>> So wat beteken dit?

122
00:05:19,540 --> 00:05:22,390
So, wat is die ergste geval scenario
vir borrelsortering, en wat is

123
00:05:22,390 --> 00:05:25,330
die beste scenario vir borrelsortering?

124
00:05:25,330 --> 00:05:27,770
Het jy dit raai?

125
00:05:27,770 --> 00:05:32,420
In die ergste geval wat jy hoef te Itereer
oor al die elemente N N tye.

126
00:05:32,420 --> 00:05:34,220
So het die ergste geval is N kwadraat.

127
00:05:34,220 --> 00:05:36,550
>> As die skikking is perfek
gesorteerde al, net jy

128
00:05:36,550 --> 00:05:38,580
het om te kyk na elke
van die elemente 'n keer.

129
00:05:38,580 --> 00:05:42,670
En as die ruil toonbank is nog 0,
jy kan sê hierdie skikking gesorteer.

130
00:05:42,670 --> 00:05:45,780
En so in die beste geval, dit is
eintlik beter as seleksie

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

132
00:05:49,230 --> 00:05:50,270
>> Ek is Doug Lloyd.

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

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