1
00:00:00,000 --> 00:00:03,360
>> [Music kucheza]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: zote haki, hivyo
Bubble aina ni algorithm

4
00:00:06,730 --> 00:00:08,730
unaweza kutumia aina seti ya vipengele.

5
00:00:08,730 --> 00:00:10,850
Hebu tuangalie jinsi kazi.

6
00:00:10,850 --> 00:00:13,240
>> Hivyo wazo la msingi la
Bubble aina ni hii.

7
00:00:13,240 --> 00:00:17,340
Sisi kwa ujumla wanataka kuhamia juu
mambo yenye thamani ujumla na haki,

8
00:00:17,340 --> 00:00:20,340
na kupunguza mambo yenye thamani ujumla
kwa upande wa kushoto, kama sisi bila kutarajia.

9
00:00:20,340 --> 00:00:23,256
Tunataka mambo ya chini kwa kuwa katika
mwanzo, na mambo ya juu

10
00:00:23,256 --> 00:00:24,970
kuwa mwishoni.

11
00:00:24,970 --> 00:00:26,130
>> Je, sisi kufanya hivyo?

12
00:00:26,130 --> 00:00:28,040
Vizuri katika pseudocode kificho,
tunaweza kusema, hebu

13
00:00:28,040 --> 00:00:30,320
kuweka wabadilishane kinyume na thamani mashirika yasiyo ya sifuri.

14
00:00:30,320 --> 00:00:32,570
Tutaweza kuona nini sisi kufanya hivyo katika pili.

15
00:00:32,570 --> 00:00:36,090
Na kisha sisi kurudia zifuatazo
mchakato mpaka wabadilishane kukabiliana ni 0,

16
00:00:36,090 --> 00:00:39,910
au mpaka sisi kufanya hakuna swaps hata kidogo.

17
00:00:39,910 --> 00:00:43,170
>> Rudisha wabadilishane kinyume na
0 kama si tayari 0.

18
00:00:43,170 --> 00:00:46,420
Kisha kuangalia kila
karibu jozi ya vipengele.

19
00:00:46,420 --> 00:00:49,550
Kama mambo hayo mawili ni
si ili, wabadilishane yao,

20
00:00:49,550 --> 00:00:51,620
na kuongeza 1 kwa wabadilishane kukabiliana.

21
00:00:51,620 --> 00:00:53,870
Kama wewe ni kufikiri kuhusu
hii kabla ya taswira yake,

22
00:00:53,870 --> 00:00:57,471
taarifa kwamba hii itakuwa hoja chini
mambo yenye thamani kwa upande wa kushoto

23
00:00:57,471 --> 00:01:00,720
na ya juu yenye thamani ya vipengele na haki,
ufanisi kufanya nini tunataka kufanya,

24
00:01:00,720 --> 00:01:03,940
ambayo ni kusonga makundi hayo
ya mambo katika njia hiyo.

25
00:01:03,940 --> 00:01:07,035
Hebu taswira jinsi hii
ili kuangalia kwa kutumia safu yetu

26
00:01:07,035 --> 00:01:10,504
kwamba sisi kutumika kwa mtihani
nje algorithms haya.

27
00:01:10,504 --> 00:01:13,420
Tuna safu zisizochambuliwa hapa tena,
unahitajika kwa wote wa mambo

28
00:01:13,420 --> 00:01:14,840
kuwa katika nyekundu.

29
00:01:14,840 --> 00:01:17,970
Na mimi kuweka wabadilishane yangu ya kukabiliana na
kwa thamani nonzero.

30
00:01:17,970 --> 00:01:20,610
Mimi kiholela alichagua
hasi 1-- siyo 0.

31
00:01:20,610 --> 00:01:23,840
Tunataka kurudia utaratibu huu
mpaka wabadilishane kukabiliana ni 0.

32
00:01:23,840 --> 00:01:26,540
Hii ni kwa nini mimi kuweka wabadilishane yangu
kinyume na baadhi thamani mashirika yasiyo ya sifuri,

33
00:01:26,540 --> 00:01:29,400
kwa sababu vinginevyo
wabadilishane kukabiliana itakuwa 0.

34
00:01:29,400 --> 00:01:31,610
Tunataka hata kuanza
mchakato wa algorithm.

35
00:01:31,610 --> 00:01:33,610
Hivyo tena, hatua are--
upya wabadilishane kukabiliana

36
00:01:33,610 --> 00:01:37,900
0, kisha kuangalia kila karibu
jozi, na kama uko nje ya utaratibu,

37
00:01:37,900 --> 00:01:40,514
wabadilishane yao, na kuongeza 1
kwa wabadilishane kukabiliana.

38
00:01:40,514 --> 00:01:41,680
Basi hebu kuanza mchakato huu.

39
00:01:41,680 --> 00:01:44,430
Hivyo jambo la kwanza sisi kufanya ni
sisi kuweka wabadilishane kinyume na 0,

40
00:01:44,430 --> 00:01:46,660
na kisha sisi kuanza kuangalia
katika kila jozi karibu.

41
00:01:46,660 --> 00:01:49,140
>> Hivyo sisi kwanza kuanza kuangalia 5 na 2.

42
00:01:49,140 --> 00:01:52,410
Tunaona kwamba wao ni nje ya
ili na hivyo sisi kubadilishana nao.

43
00:01:52,410 --> 00:01:53,830
Na sisi kuongeza 1 kwa wabadilishane kukabiliana.

44
00:01:53,830 --> 00:01:57,860
Hivyo sasa wabadilishane yetu ya kukabiliana na ni 1,
na 2 na 5 wamekuwa kimewashwa.

45
00:01:57,860 --> 00:01:59,370
Sasa sisi kurudia utaratibu tena.

46
00:01:59,370 --> 00:02:03,540
>> Sisi kuangalia ijayo jozi karibu,
5 na 1-- wao uko pia nje ya utaratibu,

47
00:02:03,540 --> 00:02:06,960
hivyo sisi wabadilishane yao na kuongeza
1 kwa wabadilishane kukabiliana.

48
00:02:06,960 --> 00:02:08,900
Kisha sisi kuangalia 5 na 3.

49
00:02:08,900 --> 00:02:13,830
Wao ni nje ya utaratibu, hivyo sisi wabadilishane
wao na sisi kuongeza 1 kwa wabadilishane kukabiliana.

50
00:02:13,830 --> 00:02:15,550
Kisha sisi kuangalia 5 na 6.

51
00:02:15,550 --> 00:02:18,630
Wao ni ili, hivyo sisi si kweli
haja wabadilishane chochote wakati huu.

52
00:02:18,630 --> 00:02:20,250
Kisha sisi kuangalia 6 na 4.

53
00:02:20,250 --> 00:02:24,920
Wao ni pia nje ya utaratibu, hivyo sisi wabadilishane
wao na sisi kuongeza 1 kwa wabadilishane kukabiliana.

54
00:02:24,920 --> 00:02:26,230
>> Sasa angalia nini kilichotokea.

55
00:02:26,230 --> 00:02:29,514
Tumekuwa wakiongozwa 6 njia yote hadi mwisho.

56
00:02:29,514 --> 00:02:32,180
Hivyo katika uteuzi aina, kama wameweza
kuonekana kwamba video, tulichokifanya ni

57
00:02:32,180 --> 00:02:35,290
sisi kuishia kusonga
mambo madogo katika jengo

58
00:02:35,290 --> 00:02:39,640
safu Iliyopangwa kimsingi kutoka
kushoto na kulia, wadogo na ukubwa.

59
00:02:39,640 --> 00:02:43,200
Katika kesi ya Bubble aina, kama tuko
kufuatia algorithm hii hasa,

60
00:02:43,200 --> 00:02:46,720
sisi ni kweli kwenda kuwa jengo
safu Iliyopangwa kutoka kulia

61
00:02:46,720 --> 00:02:49,100
kwa upande wa kushoto, kubwa na ndogo.

62
00:02:49,100 --> 00:02:53,840
Tuna ufanisi bubbled 6,
thamani kubwa, njia yote hadi mwisho.

63
00:02:53,840 --> 00:02:56,165
>> Na ili tuweze sasa kutangaza
kuwa kwamba ni yamepangwa,

64
00:02:56,165 --> 00:02:59,130
na katika siku zijazo iterations--
kwenda kwa safu again--

65
00:02:59,130 --> 00:03:01,280
hatuna kuzingatia 6 tena.

66
00:03:01,280 --> 00:03:03,850
Sisi tu kuwa na kufikiria
mambo zisizochambuliwa

67
00:03:03,850 --> 00:03:06,299
wakati sisi ni kuangalia jozi karibu.

68
00:03:06,299 --> 00:03:08,340
Hivyo tuna kumaliza moja
kupita katika Bubble aina.

69
00:03:08,340 --> 00:03:11,941
Hivyo sasa sisi kurudi nyuma kwa swali,
kurudia mpaka wabadilishane kukabiliana ni 0.

70
00:03:11,941 --> 00:03:13,690
Naam wabadilishane kukabiliana
ni 4, hivyo tunakwenda

71
00:03:13,690 --> 00:03:15,410
kuweka kurudia utaratibu huu tena.

72
00:03:15,410 --> 00:03:19,180
>> Tunakwenda upya wabadilishane kukabiliana
0, na kuangalia kila jozi karibu.

73
00:03:19,180 --> 00:03:21,890
Hivyo sisi kuanza na 2 na 1-- wao uko
nje ya utaratibu, hivyo sisi wabadilishane yao

74
00:03:21,890 --> 00:03:23,620
na sisi kuongeza 1 kwa wabadilishane kukabiliana.

75
00:03:23,620 --> 00:03:25,490
2 na 3, wao uko katika utaratibu.

76
00:03:25,490 --> 00:03:27,060
Hatuna haja ya kufanya kitu chochote.

77
00:03:27,060 --> 00:03:28,420
3 na 5 ni kwa utaratibu.

78
00:03:28,420 --> 00:03:30,150
Hatuna haja ya kufanya kitu chochote pale.

79
00:03:30,150 --> 00:03:32,515
>> 5 na 4, wao ni nje
ya utaratibu, na hivyo sisi

80
00:03:32,515 --> 00:03:35,130
haja wabadilishane yao na kuongeza
1 kwa wabadilishane kukabiliana.

81
00:03:35,130 --> 00:03:38,880
Na sasa tumekuwa wakiongozwa 5,
ijayo kubwa kipengele,

82
00:03:38,880 --> 00:03:40,920
hadi mwisho wa fungu zisizochambuliwa.

83
00:03:40,920 --> 00:03:44,360
Ili tuweze sasa wito kwamba
sehemu ya fungu yamepangwa.

84
00:03:44,360 --> 00:03:47,180
>> Sasa wewe ni kuangalia katika
screen na pengine wanaweza kuwaambia,

85
00:03:47,180 --> 00:03:50,130
kama naweza, kwamba safu
ni vyema hivi sasa.

86
00:03:50,130 --> 00:03:51,820
Lakini hatuwezi kuthibitisha kuwa bado.

87
00:03:51,820 --> 00:03:54,359
Hatuna uhakika
kwamba ni vyema.

88
00:03:54,359 --> 00:03:56,900
Lakini hii ni mahali ambapo wabadilishane
kukabiliana kinaendelea kuja katika kucheza.

89
00:03:56,900 --> 00:03:59,060
>> Hivyo tumekuwa kukamilika kupita.

90
00:03:59,060 --> 00:04:00,357
Wabadilishane kukabiliana ni 2.

91
00:04:00,357 --> 00:04:02,190
Hivyo sisi ni kwenda kurudia
mchakato huu tena,

92
00:04:02,190 --> 00:04:04,290
kurudia mpaka wabadilishane kukabiliana ni 0.

93
00:04:04,290 --> 00:04:05,550
Rudisha wabadilishane kinyume na 0.

94
00:04:05,550 --> 00:04:06,820
Hivyo tutaweza upya.

95
00:04:06,820 --> 00:04:09,810
>> Sasa tuangalie kila jozi karibu.

96
00:04:09,810 --> 00:04:11,880
Hiyo ni kwa utaratibu, 1 na 2.

97
00:04:11,880 --> 00:04:13,590
2 na 3 ni kwa utaratibu.

98
00:04:13,590 --> 00:04:15,010
3 na 4 ni kwa utaratibu.

99
00:04:15,010 --> 00:04:19,250
Hivyo katika hatua hii, taarifa tumekuwa kukamilika
kuangalia kila jozi karibu,

100
00:04:19,250 --> 00:04:22,530
lakini wabadilishane kukabiliana bado ni 0.

101
00:04:22,530 --> 00:04:25,520
>> Kama hatuwezi kuwa na kubadili
mambo yoyote, basi wao

102
00:04:25,520 --> 00:04:28,340
lazima ili, na
mujibu wa utaratibu huu.

103
00:04:28,340 --> 00:04:32,000
Na hivyo ufanisi wa kila aina,
kwamba wanasayansi sisi kompyuta upendo,

104
00:04:32,000 --> 00:04:35,560
ni sasa tunaweza kutangaza
safu nzima lazima

105
00:04:35,560 --> 00:04:38,160
kutatuliwa, kwa sababu hatukuwa
na wabadilishane mambo yoyote.

106
00:04:38,160 --> 00:04:40,380
Hiyo ni pretty nzuri.

107
00:04:40,380 --> 00:04:43,260
>> Basi nini hali mbaya
mazingira na Bubble aina?

108
00:04:43,260 --> 00:04:46,240
Katika hali mbaya zaidi safu ni
ili reverse kabisa,

109
00:04:46,240 --> 00:04:49,870
na hivyo inabidi Bubble kila
ya mambo makubwa zote

110
00:04:49,870 --> 00:04:51,780
njia hela safu.

111
00:04:51,780 --> 00:04:55,350
Na sisi kwa ufanisi pia kuwa na
Bubble wote wa mambo madogo nyuma

112
00:04:55,350 --> 00:04:57,050
njia yote katika safu, pia.

113
00:04:57,050 --> 00:05:01,950
Hivyo kila moja ya mambo n ana hoja
katika yote ya mambo mengine n.

114
00:05:01,950 --> 00:05:04,102
Hivyo hiyo ni mazingira ya kesi mbaya.

115
00:05:04,102 --> 00:05:05,810
Katika kesi bora
mazingira ingawa, hii ni

116
00:05:05,810 --> 00:05:07,880
tofauti kidogo kutoka uteuzi aina.

117
00:05:07,880 --> 00:05:10,040
Safu tayari
yamepangwa wakati sisi kwenda katika.

118
00:05:10,040 --> 00:05:12,550
Hatuna kufanya lolote
swaps juu ya kupita kwanza.

119
00:05:12,550 --> 00:05:14,940
Hivyo tuwe na kuangalia
katika mambo machache, sawa?

120
00:05:14,940 --> 00:05:18,580
Hatuna kurudia huu
mchakato idadi ya nyakati juu.

121
00:05:18,580 --> 00:05:19,540
>> Hivyo nini maana gani?

122
00:05:19,540 --> 00:05:22,390
Basi nini mazingira ya kesi mbaya
kwa Bubble aina, na nini

123
00:05:22,390 --> 00:05:25,330
bora kesi mazingira kwa Bubble aina?

124
00:05:25,330 --> 00:05:27,770
Je, nadhani hili?

125
00:05:27,770 --> 00:05:32,420
Katika hali mbaya zaidi una iterate
hela zote mambo n n mara.

126
00:05:32,420 --> 00:05:34,220
Hivyo kesi mbaya ni n squared.

127
00:05:34,220 --> 00:05:36,550
>> Kama safu ni kikamilifu
Iliyopangwa ingawa, wewe tu

128
00:05:36,550 --> 00:05:38,580
kuwa na kuangalia kila
ya mambo mara moja.

129
00:05:38,580 --> 00:05:42,670
Na kama wabadilishane kukabiliana bado ni 0,
unaweza kusema safu hii ni Iliyopangwa.

130
00:05:42,670 --> 00:05:45,780
Na hivyo katika kesi bora, hii ni
kweli bora kuliko uteuzi

131
00:05:45,780 --> 00:05:49,230
sort-- ni omega ya n.

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

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

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