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

2
00:00:02,840 --> 00:00:04,560
[Jackson STEINKAMP Harvard University]

3
00:00:04,560 --> 00:00:07,500
[ITO AY CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
-Uri-uriin ng bubble ay isang halimbawa ng algorithm ng pag-uuri-uri -

5
00:00:11,730 --> 00:00:14,460
na, ang isang pamamaraan para sa pag-uuri-uri sa isang hanay ng mga elemento sa

6
00:00:14,460 --> 00:00:15,840
pataas o pababang ayos.

7
00:00:15,840 --> 00:00:18,710
Halimbawa, kung gusto mo upang pag-uri-uriin ang isang array binubuo ng ang mga numero

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], tamang pagpapatupad ng Bubble-uri-uriin ang ibalik ang

9
00:00:23,060 --> 00:00:26,260
pinagsunod-sunod array [2, 3, 5, 9] sa pataas na pagkakasunod-sunod.

10
00:00:26,260 --> 00:00:28,850
Ngayon, ako pagpunta sa ipaliwanag sa pseudocode kung paano gumagana ang algorithm sa.

11
00:00:28,850 --> 00:00:34,000
>> Ipagpalagay natin na namin ang pag-uuri-uri ng isang listahan ng 5 integer - 3, 2, 9, 6, at 5.

12
00:00:34,000 --> 00:00:37,650
Algorithm ay nagsisimula sa pamamagitan ng pagtingin sa ang unang dalawang mga elemento, 3 at 2,

13
00:00:37,650 --> 00:00:40,850
at check kung sila ng order na may kaugnayan sa bawat isa.

14
00:00:40,850 --> 00:00:43,150
Ang mga ito ay - 3 ay mas malaki kaysa sa 2.

15
00:00:43,150 --> 00:00:45,190
Upang maging sa pataas na pagkakasunod-sunod, dapat silang maging ang iba pang mga paraan sa paligid.

16
00:00:45,190 --> 00:00:46,610
Kaya, swap namin sa kanila.

17
00:00:46,610 --> 00:00:49,760
Ngayon tinitingnan ang listahan tulad nito: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Susunod, tinitingnan namin ang pangalawa at pangatlong elemento, 3 at 9.

19
00:00:52,450 --> 00:00:55,770
Na ang mga ito sa tamang pagkakasunod-sunod na may kaugnayan sa bawat isa.

20
00:00:55,770 --> 00:00:58,800
Iyon ay, 3 ay mas mababa sa 9 kaya algorithm ay hindi swap sa kanila.

21
00:00:58,800 --> 00:01:01,900
Susunod, tinitingnan namin ang 9 at 6. Ang mga ito ng pagkakasunod-sunod.

22
00:01:01,900 --> 00:01:04,260
>> Kaya, kailangan naming i-swap sa kanila dahil 9 ay mas malaki kaysa sa 6.

23
00:01:04,260 --> 00:01:08,840
Panghuli, hanapin namin sa huling dalawang integer, 9 at 5.

24
00:01:08,840 --> 00:01:10,850
Ang mga ito ng pagkakasunod-sunod, kaya dapat sila ay swapped.

25
00:01:10,850 --> 00:01:13,360
Pagkatapos ng unang kumpletong pass sa pamamagitan ng listahan,

26
00:01:13,360 --> 00:01:17,140
Mukhang ito: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Hindi masama. Halos Ito ay pinagsunod-sunod.

28
00:01:19,690 --> 00:01:22,450
Ngunit kailangan namin upang tumakbo muli sa pamamagitan ng listahan upang makakuha ng ganap na pinagsunod-sunod.

29
00:01:22,450 --> 00:01:29,250
Dalawang ay mas mababa sa 3, kaya hindi namin swap sa kanila.

30
00:01:29,250 --> 00:01:31,700
>> Tatlong ay mas mababa sa 6, kaya hindi namin swap sa kanila.

31
00:01:31,700 --> 00:01:35,500
Anim ay mas malaki kaysa 5. Namin swapped.

32
00:01:35,500 --> 00:01:38,460
Anim ay mas mababa sa 9. Hindi namin magpalitan.

33
00:01:38,460 --> 00:01:42,170
Pagkatapos ng pangalawang pass sa pamamagitan, ay ganito ang hitsura: [2, 3, 5, 6, 9]. Perpekto.

34
00:01:42,170 --> 00:01:44,680
Ngayon, sabihin sumulat ito sa pseudocode.

35
00:01:44,680 --> 00:01:48,450
Talaga, para sa bawat elemento sa listahan, kailangan namin upang tingnan ito

36
00:01:48,450 --> 00:01:50,060
at ang mga elemento nang direkta sa kanan.

37
00:01:50,060 --> 00:01:53,420
Kung ang mga ito ay sira na may kaugnayan sa bawat isa - iyon ay, kung ang elemento sa kaliwa

38
00:01:53,420 --> 00:01:56,810
ay mas mataas kaysa sa isa sa kanan - dapat naming magpalitan ng dalawang elemento.

39
00:01:56,810 --> 00:02:01,270
>> Ginagawa namin ito para sa bawat elemento ng listahan, at gumawa kami ng isang pass sa pamamagitan ng.

40
00:02:01,270 --> 00:02:05,160
Ngayon lang namin upang gawin ang pass-through na sapat na oras upang matiyak ang listahan

41
00:02:05,160 --> 00:02:06,480
ay ganap na, maayos na pinagsunod-sunod.

42
00:02:06,480 --> 00:02:08,889
Ngunit kung gaano karaming beses ang mayroon kaming upang pumasa sa pamamagitan ng listahan

43
00:02:08,889 --> 00:02:10,400
magagarantiya na tapos na kami?

44
00:02:10,400 --> 00:02:14,730
Well, ang pinakamasama-case na sitwasyon ay kung kami ay may isang ganap na paurong listahan.

45
00:02:14,730 --> 00:02:17,840
Pagkatapos ito ay tumatagal ng isang bilang ng mga pumasa-through na katumbas ng bilang

46
00:02:17,840 --> 00:02:19,730
ng mga elemento n-1.

47
00:02:19,730 --> 00:02:24,720
Kung ito ay hindi magkaroon ng kahulugan intuitively, sa tingin ng isang simpleng kaso - ang listahan [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Ito ay pagpunta sa tumagal ng isang pass-through na upang pag-uri-uriin ang tama.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Ang pinakamasama kaso na may 3 mga elemento pinagsunod-sunod paurong,

50
00:02:33,060 --> 00:02:34,830
ito ay tumagal ng 2 iterations pagbukud-.

51
00:02:34,830 --> 00:02:37,980
Pagkatapos ng isang pag-ulit, [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Ang pangalawang magbubunga ang pinagsunod-sunod na array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Kaya alam mong hindi mo kailangang pumunta sa pamamagitan ng array, sa pangkalahatan,

54
00:02:43,350 --> 00:02:46,790
higit pa kaysa sa n-1 beses, kung saan ang n ay ang bilang ng mga elemento sa array.

55
00:02:47,090 --> 00:02:50,470
Ito ay tinatawag na-uri-uriin ng Bubble dahil ang pinakamalaking elemento ay may posibilidad na 'bubble-up'

56
00:02:50,470 --> 00:02:51,950
sa kanan medyo mabilis.

57
00:02:51,950 --> 00:02:53,980
Sa katunayan, ang algorithm na ito ay lubhang kawili-wili pag-uugali.

58
00:02:53,980 --> 00:02:57,410
>> Pagkatapos m iterations sa pamamagitan ng buong array,

59
00:02:57,410 --> 00:02:59,000
ang rightmost m elemento ay katiyakan

60
00:02:59,000 --> 00:03:01,000
na pinagsunod-sunod sa kanilang tamang lugar.

61
00:03:01,000 --> 00:03:02,280
Kung nais mong makita ito para sa iyong sarili,

62
00:03:02,280 --> 00:03:05,500
maaari naming subukan ito sa ganap na paurong listahan [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Pagkatapos ng isang pass sa pamamagitan ng buong listahan,

64
00:03:08,220 --> 00:03:09,220
[Tunog ng pagsulat]

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
rightmost elemento 9 ay nasa tamang lugar nito.

67
00:03:21,250 --> 00:03:24,760
Pagkatapos ng pangalawang pass-through, ang 6 ay may 'bubbled-up' sa

68
00:03:24,760 --> 00:03:26,220
pangalawang rightmost lugar.

69
00:03:26,220 --> 00:03:28,840
Ang dalawang mga elemento sa kanan - 6 at 9 - sa kanilang mga tamang lugar

70
00:03:28,840 --> 00:03:30,580
pagkatapos ng unang dalawang pass-through.

71
00:03:30,580 --> 00:03:32,590
>> Kaya, kung paano namin gamitin ito upang i-optimize ang algorithm?

72
00:03:32,590 --> 00:03:34,850
Well, pagkatapos ng isang pag-ulit sa pamamagitan ng array

73
00:03:34,850 --> 00:03:37,690
hindi namin aktwal na kailangan upang suriin ang rightmost elemento

74
00:03:37,690 --> 00:03:39,200
dahil alam namin ito pinagsunod-sunod.

75
00:03:39,200 --> 00:03:43,050
Pagkatapos ng dalawang iterations, alam namin para bang rightmost dalawang mga elemento sa lugar.

76
00:03:43,050 --> 00:03:48,260
Kaya, sa pangkalahatan, pagkatapos k iterations sa pamamagitan ng buong array,

77
00:03:48,260 --> 00:03:51,550
check ang huling elemento sa k ay kalabisan dahil alam namin

78
00:03:51,550 --> 00:03:52,360
ang mga ito sa tamang lokasyon.

79
00:03:52,360 --> 00:03:54,870
>> Kaya kung ikaw ay pag-uuri-uri ng isang array ng mga elemento n,

80
00:03:54,870 --> 00:03:57,870
sa unang pag-ulit - you'll upang pag-uri-uriin ang lahat ng mga elemento - ang unang n-0.

81
00:03:57,870 --> 00:04:04,170
Sa pangalawang ulit, magkakaroon ka upang tumingin sa lahat ng mga elemento ngunit ang huling -

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

83
00:04:07,090 --> 00:04:10,520
-Optimize ng isa pang maaaring upang suriin kung ang listahan na pinagsunod-sunod

84
00:04:10,520 --> 00:04:11,710
pagkatapos ng bawat pag-ulit.

85
00:04:11,710 --> 00:04:13,900
Kung ito pinagsunod-sunod, hindi namin kailangang gumawa ng anumang higit pang mga iterations

86
00:04:13,900 --> 00:04:15,310
sa pamamagitan ng listahan.

87
00:04:15,310 --> 00:04:16,220
Paano namin gawin ito?

88
00:04:16,220 --> 00:04:19,360
Well, kung hindi kami gumawa ng anumang mga swaps sa isang pass-through ng listahan,

89
00:04:19,360 --> 00:04:22,350
malinaw na listahan ay pinagsunod-sunod dahil hindi namin magpalitan ng anumang.

90
00:04:22,350 --> 00:04:24,160
Kaya tiyak namin ay hindi upang pag-uri-uriin muli.

91
00:04:24,160 --> 00:04:27,960
>> Siguro maaari mong simulan ang isang flag variable na tinatawag na 'hindi pinagsunod-sunod' sa

92
00:04:27,960 --> 00:04:30,990
mali at baguhin ito sa true kung mayroon kang magpalitan anumang mga elemento sa

93
00:04:30,990 --> 00:04:32,290
isa-ulit sa pamamagitan ng array.

94
00:04:32,290 --> 00:04:35,350
O katulad, gumawa ng isang counter sa bilang ng kung gaano karaming mga swaps gumawa ka

95
00:04:35,350 --> 00:04:37,040
sa anumang naibigay na ulit.

96
00:04:37,040 --> 00:04:40,040
Sa dulo ng isang pag-ulit, kung hindi mo swap ang alinman sa mga elemento,

97
00:04:40,040 --> 00:04:41,780
alam mo listahan na pinagsunod-sunod at tapos ka na.

98
00:04:41,780 --> 00:04:44,090
Bubble-uri-uriin, tulad ng iba pang mga pag-uuri algorithm, maaari

99
00:04:44,090 --> 00:04:46,960
tweaked upang gumana para sa anumang mga elemento na kung saan ay mayroon ng isang pag-order paraan ng.

100
00:04:46,960 --> 00:04:50,610
>> Iyon ay, naibigay dalawang elemento mayroon kang isang paraan upang sabihin kung ang unang

101
00:04:50,610 --> 00:04:53,770
ay mas malaki kaysa sa, na katumbas ng o mas mababa kaysa sa ikalawang.

102
00:04:53,770 --> 00:04:56,870
Halimbawa, maaari mong pag-uri-uriin ang mga titik ng alpabeto sa pamamagitan ng sinasabi

103
00:04:56,870 --> 00:05:00,520
na isang <b, b <c, atbp.

104
00:05:00,520 --> 00:05:03,830
O maaari mong pag-uri-uriin ang mga araw ng linggo kung saan Linggo ay mas mababa sa Lunes

105
00:05:03,830 --> 00:05:05,110
na mas mababa sa Martes.

106
00:05:05,110 --> 00:05:09,630
>> Bubble-uri-uriin ang hindi ay nangangahulugan na ang isang napaka mahusay o mabilis na pag-uuri algorithm.

107
00:05:09,630 --> 00:05:12,370
Nito pinakamasama-case runtime Big O ng n ²

108
00:05:12,370 --> 00:05:14,810
dahil mayroon kang iterations n sa pamamagitan ng isang listahan

109
00:05:14,810 --> 00:05:18,430
pagsuri ng lahat ng mga elemento n bawat pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Ito magpatakbo ng oras ay nangangahulugan na ang bilang ang bilang ng mga elemento ay pag-uuri-uri ng mga pagtaas,

111
00:05:22,730 --> 00:05:24,330
ang run ng oras ay nagdaragdag quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Ngunit kung ang kahusayan ay hindi isang pangunahing alalahanin ng iyong programa

113
00:05:27,330 --> 00:05:29,550
o kung ka lamang pag-uuri-uri ng maliit na bilang ng mga elemento,

114
00:05:29,550 --> 00:05:31,660
maaari mong mahanap ang kapaki-pakinabang ang Bubble-uri-uriin ang dahil

115
00:05:31,660 --> 00:05:33,360
ito ay isa ng ang pinakasimpleng pag-uuri algorithm upang maunawaan

116
00:05:33,360 --> 00:05:34,250
at code.

117
00:05:34,250 --> 00:05:37,270
Ring isang mahusay na paraan upang makakuha ng karanasan sa nagta-translate ng isang panteorya

118
00:05:37,270 --> 00:05:40,220
algorithm sa aktwal na code sa paggana.

119
00:05:40,220 --> 00:05:43,000
Well, na Bubble Pagbukud-bukurin para sa iyo. Salamat para sa panonood.

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