1
00:00:00,000 --> 00:00:03,360
>> [MUZIKO Ludante]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Bone, do
bobelo varo estas algoritmo

4
00:00:06,730 --> 00:00:08,730
vi povas uzi por ordigi aro de elementoj.

5
00:00:08,730 --> 00:00:10,850
Ni rigardu kiel ĝi funkcias.

6
00:00:10,850 --> 00:00:13,240
>> Do la baza ideo malantaŭ
bobelo varo estas tiu.

7
00:00:13,240 --> 00:00:17,340
Ni ĝenerale deziras movi altaj
valoraj elementoj ĝenerale al la dekstra,

8
00:00:17,340 --> 00:00:20,340
kaj malaltigi valoraj elementoj ĝenerale
maldekstren, kiel ni atendus.

9
00:00:20,340 --> 00:00:23,256
Ni volas la malsupra aferojn esti ĉe
la komenco, kaj la pli altaj aferoj

10
00:00:23,256 --> 00:00:24,970
esti fine.

11
00:00:24,970 --> 00:00:26,130
>> Kiel ni faru tion?

12
00:00:26,130 --> 00:00:28,040
Nu en _pseudocode_ kodo,
ni povus diri, ni

13
00:00:28,040 --> 00:00:30,320
fiksi interŝanĝa vendotablo al ne-nula valoro.

14
00:00:30,320 --> 00:00:32,570
Ni vidos kial ni faru tion en dua.

15
00:00:32,570 --> 00:00:36,090
Kaj tiam ni ripetu la jenaj
procezo ĝis la interŝanĝa vendotablo estas 0,

16
00:00:36,090 --> 00:00:39,910
aŭ ĝis ni faru svopoj ajn.

17
00:00:39,910 --> 00:00:43,170
>> Restarigi la interŝanĝa kontraŭas
0 se ĝi ne estas jam 0.

18
00:00:43,170 --> 00:00:46,420
Tiam rigardi ĉiun
apuda paro de elementoj.

19
00:00:46,420 --> 00:00:49,550
Se tiuj du elementoj estas
ne en ordo, interŝanĝi ilin,

20
00:00:49,550 --> 00:00:51,620
kaj aldoni 1 al la vendotablo interŝanĝa.

21
00:00:51,620 --> 00:00:53,870
Se vi pensas pri
tiu antaŭ vi bildigi ĝin,

22
00:00:53,870 --> 00:00:57,471
rimarki ke tiu movos malsupra
valoraj elementoj maldekstren

23
00:00:57,471 --> 00:01:00,720
kaj alta takso elementojn al la dekstra,
efike fari kion ni volas fari,

24
00:01:00,720 --> 00:01:03,940
kio estas movi tiuj grupoj
de elementoj en tiu maniero.

25
00:01:03,940 --> 00:01:07,035
Ni visualizar kiel ĉi
povus rigardi uzante nia tabelo

26
00:01:07,035 --> 00:01:10,504
ke ni kutimis testi
el tiuj algoritmoj.

27
00:01:10,504 --> 00:01:13,420
Ni havas unsorted tabelo tien;
indikita de ĉiuj de la elementoj

28
00:01:13,420 --> 00:01:14,840
estante en ruĝa.

29
00:01:14,840 --> 00:01:17,970
Kaj mi turnis mian interŝanĝa vendotablo
por nenula valoro.

30
00:01:17,970 --> 00:01:20,610
Mi arbitre elektis
negativa 1-- ĝi ne estas 0.

31
00:01:20,610 --> 00:01:23,840
Ni volas ripeti tiun procezon
ĝis la interŝanĝa vendotablo estas 0.

32
00:01:23,840 --> 00:01:26,540
Tial mi starigis mian swap
vendotablo al iu ne-nula valoro,

33
00:01:26,540 --> 00:01:29,400
ĉar alie la
interŝanĝa vendotablo estus 0.

34
00:01:29,400 --> 00:01:31,610
Ni eĉ ne komenci la
procezo de la algoritmo.

35
00:01:31,610 --> 00:01:33,610
Do denove, la paŝoj are--
retrovu la interŝanĝa vendotablo

36
00:01:33,610 --> 00:01:37,900
al 0, tiam rigardu ĉiun apuda
paro, kaj se ili estas el ordo,

37
00:01:37,900 --> 00:01:40,514
interŝanĝi ilin, kaj aldonu 1
al la interŝanĝa vendotablo.

38
00:01:40,514 --> 00:01:41,680
Do ni komencu ĉi procezo.

39
00:01:41,680 --> 00:01:44,430
Do la unua afero ni fari estas
Ni starigu la interŝanĝa vendotablo al 0,

40
00:01:44,430 --> 00:01:46,660
kaj poste ni komencas rigardanta
ĉe ĉiu najbara paro.

41
00:01:46,660 --> 00:01:49,140
>> Do ni unue komenci rigardi 5 kaj 2.

42
00:01:49,140 --> 00:01:52,410
Ni vidas ke ili estas el
ordigi kaj tiel ni interŝanĝi ilin.

43
00:01:52,410 --> 00:01:53,830
Kaj ni aldonas 1 al la interŝanĝa vendotablo.

44
00:01:53,830 --> 00:01:57,860
Do nun nia interŝanĝa vendotablo estas 1,
kaj 2 kaj 5 estis interŝanĝita.

45
00:01:57,860 --> 00:01:59,370
Nun ni ripetos la procezon denove.

46
00:01:59,370 --> 00:02:03,540
>> Ni rigardas la sekva apuda paro,
5 kaj 1-- ili estas ankaŭ el ordo,

47
00:02:03,540 --> 00:02:06,960
do ni interŝanĝi ilin kaj aldoni
1 por la interŝanĝa vendotablo.

48
00:02:06,960 --> 00:02:08,900
Tiam ni rigardas 5 kaj 3.

49
00:02:08,900 --> 00:02:13,830
Ili estas el ordo, Do ni interŝanĝu
ili kaj ni aldonas 1 al la interŝanĝa vendotablo.

50
00:02:13,830 --> 00:02:15,550
Tiam ni rigardas 5 kaj 6.

51
00:02:15,550 --> 00:02:18,630
Ili estas en ordo, do ni ne vere
bezonas interŝanĝi ion ĉi tempo.

52
00:02:18,630 --> 00:02:20,250
Tiam ni rigardas 6 kaj 4.

53
00:02:20,250 --> 00:02:24,920
Ili estas ankaŭ el ordo, Do ni interŝanĝu
ili kaj ni aldonas 1 al la interŝanĝa vendotablo.

54
00:02:24,920 --> 00:02:26,230
>> Nun rimarki kio okazis.

55
00:02:26,230 --> 00:02:29,514
Ni translokiĝis 6 tutan vojon al la fino.

56
00:02:29,514 --> 00:02:32,180
Do selektado speco, se vi havas
vidis ke filmetoj, kion ni faris estis

57
00:02:32,180 --> 00:02:35,290
ni finis kopiante la
malgrandaj elementoj en konstruaĵo

58
00:02:35,290 --> 00:02:39,640
la ordo tabelo esence el
maldekstre dekstren, la plej malgranda al plej granda.

59
00:02:39,640 --> 00:02:43,200
En la kazo de bobelo varon, se ni estas
sekvante tiu aparta algoritmo,

60
00:02:43,200 --> 00:02:46,720
Ni efektive tuj estos konstruado
la ordo tabelo de dekstra

61
00:02:46,720 --> 00:02:49,100
al maldekstra, granda ol plej malgranda.

62
00:02:49,100 --> 00:02:53,840
Ni efike bobelis 6, La
plej granda valoro, la tutan vojon al la fino.

63
00:02:53,840 --> 00:02:56,165
>> Kaj tiel ni povas nun deklari
ke kiu ordigataj

64
00:02:56,165 --> 00:02:59,130
kaj en estonteco iterations--
irante tra la tabelo again--

65
00:02:59,130 --> 00:03:01,280
ni ne devas konsideri 6 anymore.

66
00:03:01,280 --> 00:03:03,850
Ni nur devas konsideri
la unsorted elementoj

67
00:03:03,850 --> 00:03:06,299
kiam ni rigardas najbaraj paroj.

68
00:03:06,299 --> 00:03:08,340
Do ni finis unu
trapasi bobelo varon.

69
00:03:08,340 --> 00:03:11,941
Do nun ni reiros al la demando,
ripeti ĝis la interŝanĝa vendotablo estas 0.

70
00:03:11,941 --> 00:03:13,690
Nu la interŝanĝa vendotablo
estas 4, do ni tuj

71
00:03:13,690 --> 00:03:15,410
teni ripetante tiun procezon denove.

72
00:03:15,410 --> 00:03:19,180
>> Ni tuj reagordi la interŝanĝa vendotablo
al 0, kaj aspektas ĉe ĉiu najbara paro.

73
00:03:19,180 --> 00:03:21,890
Do ni komencu per 2 kaj 1-- ili estas
el ordo, Do ni interŝanĝu ilin

74
00:03:21,890 --> 00:03:23,620
kaj ni aldonas 1 al la interŝanĝa vendotablo.

75
00:03:23,620 --> 00:03:25,490
2 kaj 3, ili estas en ordo.

76
00:03:25,490 --> 00:03:27,060
Ni ne bezonas fari ion.

77
00:03:27,060 --> 00:03:28,420
3 kaj 5 estas en ordo.

78
00:03:28,420 --> 00:03:30,150
Ni ne bezonas fari ion tie.

79
00:03:30,150 --> 00:03:32,515
>> 5 kaj 4, ili estas ekstere
de ordo, kaj tiel ni

80
00:03:32,515 --> 00:03:35,130
bezonas interŝanĝi ilin kaj aldoni
1 por la interŝanĝa vendotablo.

81
00:03:35,130 --> 00:03:38,880
Kaj nun ni movis 5,
la sekva plej granda ero,

82
00:03:38,880 --> 00:03:40,920
al la fino de la unsorted porcion.

83
00:03:40,920 --> 00:03:44,360
Do ni povas nun nomas
parto de la ordo parton.

84
00:03:44,360 --> 00:03:47,180
>> Nun vi rigardas la
ekrano kaj probable povas diri,

85
00:03:47,180 --> 00:03:50,130
kiel mi povas, ke la tabelo
estas ordo nun.

86
00:03:50,130 --> 00:03:51,820
Sed ni ne povas pruvi ke ankoraŭ.

87
00:03:51,820 --> 00:03:54,359
Ni ne havas garantion
ke ĝi estas ordo.

88
00:03:54,359 --> 00:03:56,900
Sed ĉi tiu estas kie la interŝanĝa
vendotablo tuj veni en ludon.

89
00:03:56,900 --> 00:03:59,060
>> Do ni kompletigis enirpermesilon.

90
00:03:59,060 --> 00:04:00,357
La interŝanĝa vendotablo estas 2.

91
00:04:00,357 --> 00:04:02,190
Do ni tuj ripetas
tiu procezo denove,

92
00:04:02,190 --> 00:04:04,290
ripeti ĝis la interŝanĝa vendotablo estas 0.

93
00:04:04,290 --> 00:04:05,550
Restarigi la interŝanĝa vendotablo al 0.

94
00:04:05,550 --> 00:04:06,820
Do ni reagordi ĝin.

95
00:04:06,820 --> 00:04:09,810
>> Nun rigardu ĉiu najbara paro.

96
00:04:09,810 --> 00:04:11,880
Tio en ordo, 1 kaj 2.

97
00:04:11,880 --> 00:04:13,590
2 kaj 3 estas en ordo.

98
00:04:13,590 --> 00:04:15,010
3 kaj 4 estas en ordo.

99
00:04:15,010 --> 00:04:19,250
Do en ĉi tiu punkto, ni rimarkos kompletigita
rigardante ĉiu apuda paro,

100
00:04:19,250 --> 00:04:22,530
sed la interŝanĝa vendotablo estas ankoraŭ 0.

101
00:04:22,530 --> 00:04:25,520
>> Se ni ne devas ŝanĝi
ajna elementoj, tiam ili

102
00:04:25,520 --> 00:04:28,340
devas esti en ordo, de
virto de tiu procezo.

103
00:04:28,340 --> 00:04:32,000
Kaj tial efikeco de varoj,
ke ni komputikistoj ami,

104
00:04:32,000 --> 00:04:35,560
Estas ni povas nun deklari
la tuta tabelo devas

105
00:04:35,560 --> 00:04:38,160
esti ordo, ĉar ni ne
devi interŝanĝi ajnan elementoj.

106
00:04:38,160 --> 00:04:40,380
Tio estas sufiĉe bela.

107
00:04:40,380 --> 00:04:43,260
>> Do kio estas la plej malbona kazo
scenaro kun bobelo varo?

108
00:04:43,260 --> 00:04:46,240
En la plej malbona kazo la tabelo estas
en tute inversa ordo,

109
00:04:46,240 --> 00:04:49,870
kaj do ni devas bobelo ĉiu
de la grandaj elementoj ĉiuj

110
00:04:49,870 --> 00:04:51,780
la vojo trans la tabelo.

111
00:04:51,780 --> 00:04:55,350
Kaj ni efike ankaŭ devas
bobelo ĉiujn la malgrandaj elementoj reen

112
00:04:55,350 --> 00:04:57,050
tutan vojon tra la vicojn, ankaŭ.

113
00:04:57,050 --> 00:05:01,950
Do ĉiu el la n elementoj devas movi
tra ĉiuj de la aliaj n elementoj.

114
00:05:01,950 --> 00:05:04,102
Do jen la plej malbona kazo scenaron.

115
00:05:04,102 --> 00:05:05,810
En la plej bona kazo
scenaro tamen, tiu estas

116
00:05:05,810 --> 00:05:07,880
iomete malsama de selektado varon.

117
00:05:07,880 --> 00:05:10,040
La tabelo estas jam
ordo kiam ni iros.

118
00:05:10,040 --> 00:05:12,550
Ni ne devas fari ajnan
svopoj sur la unuan enirpermesilon.

119
00:05:12,550 --> 00:05:14,940
Do ni eble devus rigardi
ĉe pli malmultaj elementoj, ĉu ne?

120
00:05:14,940 --> 00:05:18,580
Ni ne devas ripeti tiun
procesi plurajn fojojn super.

121
00:05:18,580 --> 00:05:19,540
>> Do kion tio signifas?

122
00:05:19,540 --> 00:05:22,390
Do kio estas la plej malbona kazo scenaro
por bobelo varo, kaj kio estas

123
00:05:22,390 --> 00:05:25,330
la plej bona kazo scenaro por bobelo varo?

124
00:05:25,330 --> 00:05:27,770
Ĉu vi povas diveni tion?

125
00:05:27,770 --> 00:05:32,420
En la plej malbona kazo vi devas persisti
trans ĉiuj n elementoj n fojojn.

126
00:05:32,420 --> 00:05:34,220
Do la plej malbona kazo estas n kvadratoj.

127
00:05:34,220 --> 00:05:36,550
>> Se la tabelo estas perfekte
ordo tamen, vi nur

128
00:05:36,550 --> 00:05:38,580
devas rigardi ĉiun
de la elementoj tuj.

129
00:05:38,580 --> 00:05:42,670
Kaj se la interŝanĝa vendotablo estas ankoraŭ 0,
vi povas diri ĉi tabelo estas ordigita.

130
00:05:42,670 --> 00:05:45,780
Kaj tiel en la plej bona kazo, tiu estas
efektive pli bona ol selektado

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

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

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

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