1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Bubble aina]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[HII NI CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Panga ni mfano wa algorithm kuchagua -

5
00:00:11,730 --> 00:00:14,460
kwamba ni, utaratibu kwa ajili ya kuchagua seti ya vipengele katika

6
00:00:14,460 --> 00:00:15,840
wakipanda au kushuka ili.

7
00:00:15,840 --> 00:00:18,710
Kwa mfano, kama alitaka kutatua safu yenye namba

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], utekelezaji sahihi wa aina Bubble atarudi

9
00:00:23,060 --> 00:00:26,260
Iliyopangwa safu [2, 3, 5, 9] katika wakipanda ili.

10
00:00:26,260 --> 00:00:28,850
Sasa, mimi naenda kueleza katika pseudocode jinsi algorithm kazi.

11
00:00:28,850 --> 00:00:34,000
>> Hebu sema tuko kuchagua orodha ya integers 5-3, 2, 9, 6, na 5.

12
00:00:34,000 --> 00:00:37,650
algorithm kuanza kwa kuangalia mambo mawili ya kwanza, 3 na 2,

13
00:00:37,650 --> 00:00:40,850
na kuangalia kama uko nje ya utaratibu jamaa na kila mmoja.

14
00:00:40,850 --> 00:00:43,150
Wao ni - 3, ni mkubwa kuliko 2.

15
00:00:43,150 --> 00:00:45,190
Kuwa ili wakipanda, wanapaswa kuwa na njia nyingine kote.

16
00:00:45,190 --> 00:00:46,610
Hivyo, sisi byta yao.

17
00:00:46,610 --> 00:00:49,760
Sasa orodha inaonekana kama hii: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Next, sisi kuangalia vipengele pili na wa tatu, 3 na 9.

19
00:00:52,450 --> 00:00:55,770
Wao ni katika mpangilio sahihi jamaa na kila mmoja.

20
00:00:55,770 --> 00:00:58,800
Hiyo ni, 3 ni chini ya 9 hivyo algorithm haina byta yao.

21
00:00:58,800 --> 00:01:01,900
Next, sisi kuangalia 9 na 6. Wao ni nje ya utaratibu.

22
00:01:01,900 --> 00:01:04,260
>> Hivyo, tunahitaji wabadilishane yao kwa sababu 9, ni mkubwa kuliko 6.

23
00:01:04,260 --> 00:01:08,840
Mwisho, sisi kuangalia integers miwili iliyopita, 9 na 5.

24
00:01:08,840 --> 00:01:10,850
Wao ni nje ya utaratibu, hivyo ni lazima swapped.

25
00:01:10,850 --> 00:01:13,360
Baada ya kwanza kupita kamili kupitia orodha,

26
00:01:13,360 --> 00:01:17,140
inaonekana kama hii: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Si mbaya. Ni karibu Iliyopangwa.

28
00:01:19,690 --> 00:01:22,450
Lakini tunahitaji kukimbia kupitia orodha tena ya kupata hiyo kabisa Iliyopangwa.

29
00:01:22,450 --> 00:01:29,250
Mbili ni chini ya 3, hivyo hatuna byta yao.

30
00:01:29,250 --> 00:01:31,700
>> Tatu ni chini ya 6, hivyo hatuna byta yao.

31
00:01:31,700 --> 00:01:35,500
Sita, ni mkubwa kuliko 5. Sisi swapped.

32
00:01:35,500 --> 00:01:38,460
Sita ni chini ya 9. Hatuna wabadilishane.

33
00:01:38,460 --> 00:01:42,170
Baada ya kupita pili kupitia, inaonekana kama hii: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Sasa, hebu andika katika pseudocode.

35
00:01:44,680 --> 00:01:48,450
Kimsingi, kwa kila kipengele katika orodha, tunahitaji kuangalia ni

36
00:01:48,450 --> 00:01:50,060
na kipengele moja kwa moja na haki yake.

37
00:01:50,060 --> 00:01:53,420
Kama wao ni nje ya utaratibu jamaa na kila mmoja - yaani kama kipengele juu ya kushoto

38
00:01:53,420 --> 00:01:56,810
ni mkubwa kuliko mmoja kulia - tunapaswa wabadilishane mambo mawili.

39
00:01:56,810 --> 00:02:01,270
>> Sisi kufanya hili kwa kila kipengele cha orodha, na tumekuwa alifanya moja kupita.

40
00:02:01,270 --> 00:02:05,160
Sasa sisi tu kufanya kupitisha-kupitia mara ya kutosha kuhakikisha orodha

41
00:02:05,160 --> 00:02:06,480
kikamilifu, ipasavyo Iliyopangwa.

42
00:02:06,480 --> 00:02:08,889
Lakini mara ngapi Je, tuna kupita katika orodha ya

43
00:02:08,889 --> 00:02:10,400
kuthibitisha kwamba sisi ni kosa?

44
00:02:10,400 --> 00:02:14,730
Naam, hali mbaya zaidi kesi ni kama tuna orodha kabisa nyuma.

45
00:02:14,730 --> 00:02:17,840
Kisha inachukua idadi ya kupita throughs-sawa na idadi

46
00:02:17,840 --> 00:02:19,730
ya mambo ya n-1.

47
00:02:19,730 --> 00:02:24,720
Kama hii haina mantiki intuitively, kufikiri ya kesi rahisi - orodha [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Hii ni kwenda kuchukua kupitisha moja-kwa njia ya kutatua usahihi.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - kesi mbaya zaidi ni kwamba pamoja na mambo 3 sorted nyuma,

50
00:02:33,060 --> 00:02:34,830
ni kwenda kuchukua iterations 2 kwa aina.

51
00:02:34,830 --> 00:02:37,980
Baada iteration moja, ni [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
mavuno ya pili safu sorted [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Hivyo unajua kamwe kwenda kupitia safu, kwa ujumla,

54
00:02:43,350 --> 00:02:46,790
zaidi ya mara n-1, ambapo n ni idadi ya vipengele katika safu.

55
00:02:47,090 --> 00:02:50,470
Ni wito Bubble Panga kwa sababu vipengele kubwa huwa na 'Bubble-up'

56
00:02:50,470 --> 00:02:51,950
kwa haki pretty haraka.

57
00:02:51,950 --> 00:02:53,980
Kwa kweli, algorithm hii ina kuvutia sana tabia.

58
00:02:53,980 --> 00:02:57,410
>> Baada iterations m kupitia safu nzima,

59
00:02:57,410 --> 00:02:59,000
rightmost vipengele m uhakika

60
00:02:59,000 --> 00:03:01,000
sorted katika nafasi zao sahihi.

61
00:03:01,000 --> 00:03:02,280
Kama unataka hii kuona mwenyewe,

62
00:03:02,280 --> 00:03:05,500
tunaweza kujaribu katika orodha ya nyuma kabisa [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Baada ya kupitisha moja kwa njia ya orodha nzima,

64
00:03:08,220 --> 00:03:09,220
[Sauti ya kuandika]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
kipengele rightmost 9 ni katika nafasi yake sahihi.

67
00:03:21,250 --> 00:03:24,760
Baada ya pili kupitisha-kupitia, 6 itakuwa na 'bubbled-up' kwa

68
00:03:24,760 --> 00:03:26,220
pili rightmost mahali.

69
00:03:26,220 --> 00:03:28,840
mambo mawili juu ya haki - 6 na 9 - itakuwa katika maeneo yao sahihi

70
00:03:28,840 --> 00:03:30,580
baada ya kwanza mbili kupita-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Hivyo, jinsi gani tunaweza kutumia hii optimize algorithm?

72
00:03:32,590 --> 00:03:34,850
Naam, baada ya mmoja iteration kupitia safu

73
00:03:34,850 --> 00:03:37,690
sisi si kweli haja ya kuangalia kipengele rightmost

74
00:03:37,690 --> 00:03:39,200
kwa sababu tunajua ni Iliyopangwa.

75
00:03:39,200 --> 00:03:43,050
Baada iterations mbili, tunaweza kujua kwa uhakika rightmost mawili muhimu ni katika mahali.

76
00:03:43,050 --> 00:03:48,260
Hivyo, kwa ujumla, baada ya k iterations kupitia safu kamili,

77
00:03:48,260 --> 00:03:51,550
kuangalia vipengele k mwisho ni redundant tangu tunajua

78
00:03:51,550 --> 00:03:52,360
wao uko katika eneo sahihi tayari.

79
00:03:52,360 --> 00:03:54,870
>> Hivyo kama wewe ni kuchagua safu ya vipengele n,

80
00:03:54,870 --> 00:03:57,870
juu ya iteration kwanza - you'll kuwa na kuchambua wote wa mambo - kwanza n-0.

81
00:03:57,870 --> 00:04:04,170
On iteration pili, itabidi kuangalia wote wa mambo lakini mwisho -

82
00:04:04,170 --> 00:04:07,090
kwanza n-1.

83
00:04:07,090 --> 00:04:10,520
Optimization mwingine inaweza kuwa kwa kuangalia kama orodha tayari sorted

84
00:04:10,520 --> 00:04:11,710
baada ya kila iteration.

85
00:04:11,710 --> 00:04:13,900
Kama ni tayari Iliyopangwa, hatuna haja ya kufanya iterations yoyote zaidi

86
00:04:13,900 --> 00:04:15,310
kupitia orodha.

87
00:04:15,310 --> 00:04:16,220
Tunawezaje kufanya hivyo?

88
00:04:16,220 --> 00:04:19,360
Naam, kama sisi hatuwezi kufanya swaps yoyote juu ya kupitisha-kwa njia ya orodha,

89
00:04:19,360 --> 00:04:22,350
ni wazi kuwa orodha tayari alikuwa Iliyopangwa kwa sababu hatukuwa wabadilishane chochote.

90
00:04:22,350 --> 00:04:24,160
Hivyo sisi dhahiri hawana kutatua tena.

91
00:04:24,160 --> 00:04:27,960
>> Pengine unaweza initialize variable bendera iitwayo 'si vyema' kwa

92
00:04:27,960 --> 00:04:30,990
uongo na kubadilisha kwa kweli kama una wabadilishane vipengele yoyote juu ya

93
00:04:30,990 --> 00:04:32,290
moja iteration kupitia safu.

94
00:04:32,290 --> 00:04:35,350
Au vile vile, kufanya kinyume na uhesabu swaps kufanya

95
00:04:35,350 --> 00:04:37,040
yoyote iteration aliyopewa.

96
00:04:37,040 --> 00:04:40,040
Wakati wa mwisho wa iteration, ikiwa hakuwa wabadilishane yoyote ya vipengele,

97
00:04:40,040 --> 00:04:41,780
unajua orodha tayari sorted na wewe ni kosa.

98
00:04:41,780 --> 00:04:44,090
Bubble Panga, kama algorithms nyingine kuchagua, unaweza kuwa

99
00:04:44,090 --> 00:04:46,960
tweaked kufanya kazi kwa ajili ya mambo yoyote ambayo yana njia kuagiza.

100
00:04:46,960 --> 00:04:50,610
>> Hiyo ni, kutokana na mambo mawili muhimu una njia kusema kama moja ya kwanza

101
00:04:50,610 --> 00:04:53,770
ni mkubwa kuliko, sawa au chini ya pili.

102
00:04:53,770 --> 00:04:56,870
Kwa mfano, unaweza kutatua wa alfabeti kwa kusema

103
00:04:56,870 --> 00:05:00,520
kwamba <b, b <c, nk

104
00:05:00,520 --> 00:05:03,830
Au unaweza kutatua siku ya wiki ambapo Jumapili ni chini ya Jumatatu

105
00:05:03,830 --> 00:05:05,110
ambayo ni chini ya Jumanne.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Panga ni kwa maana hakuna ufanisi sana au kufunga kuchagua algorithm.

107
00:05:09,630 --> 00:05:12,370
Mbaya wake-kesi Runtime ni Kubwa O ya n ²

108
00:05:12,370 --> 00:05:14,810
kwa sababu una kufanya iterations n kupitia orodha

109
00:05:14,810 --> 00:05:18,430
kuangalia vipengele vyote n kila kupitisha-kupitia, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Hii wakati kukimbia ina maana kwamba kama idadi ya vipengele wewe ni kuchagua kuongezeka,

111
00:05:22,730 --> 00:05:24,330
wakati kukimbia huongeza quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Lakini kama ufanisi si tatizo kubwa ya mpango wako

113
00:05:27,330 --> 00:05:29,550
au kama wewe ni tu kuchagua idadi ndogo ya vipengele,

114
00:05:29,550 --> 00:05:31,660
unaweza kupata Bubble Panga muhimu kwa sababu

115
00:05:31,660 --> 00:05:33,360
ni moja ya algorithms rahisi kuchagua kuelewa

116
00:05:33,360 --> 00:05:34,250
na kwa kificho.

117
00:05:34,250 --> 00:05:37,270
Ni pia ni njia kubwa ya kupata uzoefu na kutafsiri nadharia

118
00:05:37,270 --> 00:05:40,220
algorithm katika kanuni halisi inayofanya kazi.

119
00:05:40,220 --> 00:05:43,000
Naam, hiyo ni Bubble Panga kwa ajili yenu. Shukrani kwa ajili ya kuangalia.

120
00:05:43,000 --> 00:05:44,000
CS50.TV