1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Triye jarèt]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Inivèsite Harvard]

3
00:00:04,560 --> 00:00:07,500
[SA A SE CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Triye jarèt ki se yon egzanp yon algorithm Fouye -

5
00:00:11,730 --> 00:00:14,460
ki se, yon pwosedi pou Fouye yon seri eleman nan yon

6
00:00:14,460 --> 00:00:15,840
moute desann oswa lòd.

7
00:00:15,840 --> 00:00:18,710
Pou egzanp, si ou te vle sòt yon etalaj ki gen ladan nimewo yo

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], yon aplikasyon kòrèk la nan Triye Bubble ta retounen nan

9
00:00:23,060 --> 00:00:26,260
Ranje etalaj [2, 3, 5, 9] nan Ascending lòd.

10
00:00:26,260 --> 00:00:28,850
Koulye a, mwen pral eksplike nan pseudocode ki jan algorithm a travay.

11
00:00:28,850 --> 00:00:34,000
>> Se pou nou di nou ap Fouye yon lis 5 nonm antye relatif - 3, 2, 9, 6, ak 5.

12
00:00:34,000 --> 00:00:37,650
Algorithm la kòmanse pa gade nan de eleman yo an premye, 3 ak 2,

13
00:00:37,650 --> 00:00:40,850
epi tyeke si yo ap soti nan lòd relatif nan chak lòt.

14
00:00:40,850 --> 00:00:43,150
Yo se - 3 pi gran pase 2.

15
00:00:43,150 --> 00:00:45,190
Pou yo kapab nan lòd montangn yo, yo ta dwe nan lòt fason alantou.

16
00:00:45,190 --> 00:00:46,610
Se konsa, nou boukante yo.

17
00:00:46,610 --> 00:00:49,760
Koulye a, lis la sanble tankou sa a: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Next, nou gade nan eleman yo, dezyèm ak twazyèm 3 ak 9.

19
00:00:52,450 --> 00:00:55,770
Yo ap nan lòd ki kòrèk relatif nan chak lòt.

20
00:00:55,770 --> 00:00:58,800
Sa se, 3 se mwens pase 9 Se konsa algorithm a pa boukante yo.

21
00:00:58,800 --> 00:01:01,900
Next, nou gade nan 9 ak 6. Yo ap parèt nan lòd.

22
00:01:01,900 --> 00:01:04,260
>> Se konsa,, nou bezwen swap yo paske 9 pi gran pase 6.

23
00:01:04,260 --> 00:01:08,840
Anfen, nou gade nan de nonb antye ki sot pase yo, 9 ak 5.

24
00:01:08,840 --> 00:01:10,850
Yo ap soti nan lòd, se konsa yo dwe échanges.

25
00:01:10,850 --> 00:01:13,360
Apre premye pas konplè a nan lis la,

26
00:01:13,360 --> 00:01:17,140
li sanble tankou sa a: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Pa move. Li nan prèske Ranje.

28
00:01:19,690 --> 00:01:22,450
Men, nou bezwen kouri nan lis la ankò jwenn li konplètman Ranje.

29
00:01:22,450 --> 00:01:29,250
De se mwens pase 3, donk nou pa boukante yo.

30
00:01:29,250 --> 00:01:31,700
>> Twa gen mwens pase 6, donk nou pa boukante yo.

31
00:01:31,700 --> 00:01:35,500
Sis gen plis pouvwa pase 5. Nou échanges.

32
00:01:35,500 --> 00:01:38,460
Sis se mwens pase 9. Nou pa boukante.

33
00:01:38,460 --> 00:01:42,170
Apre pas nan dezyèm nan, li sanble tankou sa a: [2, 3, 5, 6, 9]. Pafè.

34
00:01:42,170 --> 00:01:44,680
Koulye a, kite nan ekri li nan pseudocode.

35
00:01:44,680 --> 00:01:48,450
Fondamantalman, pou chak eleman nan lis la, nou bezwen gade nan li

36
00:01:48,450 --> 00:01:50,060
ak eleman la dirèkteman a dwat li yo.

37
00:01:50,060 --> 00:01:53,420
Si yo soti nan lòd relatif nan chak lòt - ki se, si eleman nan sou bò gòch la

38
00:01:53,420 --> 00:01:56,810
se pi plis pase youn nan sou bò dwat la - nou ta dwe swap eleman yo de.

39
00:01:56,810 --> 00:02:01,270
>> Nou fè sa pou chak eleman nan lis la, epi nou te fè yon sèl pase nan.

40
00:02:01,270 --> 00:02:05,160
Koulye a, nou jis gen nan fè pass-through fwa yo ase yo asire lis la

41
00:02:05,160 --> 00:02:06,480
se okonplè, byen Ranje.

42
00:02:06,480 --> 00:02:08,889
Men, konbyen fwa nou gen la pase sou lis la

43
00:02:08,889 --> 00:02:10,400
garanti ke nou ap fè konsa?

44
00:02:10,400 --> 00:02:14,730
Oke, senaryo ki pi mal la-ka se si nou gen yon lis konplètman bak.

45
00:02:14,730 --> 00:02:17,840
Lè sa a, li pran yon kantite pase kuvèt-egal a nimewo a

46
00:02:17,840 --> 00:02:19,730
nan eleman n-1.

47
00:02:19,730 --> 00:02:24,720
Si sa a pa fè sans intuitivement, panse a yon ka senp - lis la [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Sa a se pral pran yon sèl pass-through sòt kòrèkteman.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - ka ki pi mal se ke ak 3 eleman Ranje bak,

50
00:02:33,060 --> 00:02:34,830
li nan pral pran 2 itérations zèl.

51
00:02:34,830 --> 00:02:37,980
Apre yon sèl iterasyon, li la [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Pwodiksyon an nan dezyèm etalaj la Ranje [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Se konsa, ou konnen ou pa janm gen yo ale nan etalaj la, an jeneral,

54
00:02:43,350 --> 00:02:46,790
plis pase n-1 fwa, kote n se nimewo a eleman nan yon etalaj la.

55
00:02:47,090 --> 00:02:50,470
Yo rele li Triye Bubble paske eleman yo pi gwo yo gen tandans 'jarèt-up'

56
00:02:50,470 --> 00:02:51,950
sou bò dwat la yo byen vit.

57
00:02:51,950 --> 00:02:53,980
An reyalite, sa a algorithm gen konpòtman trè enteresan.

58
00:02:53,980 --> 00:02:57,410
>> Apre itérations m nan etalaj la an antye,

59
00:02:57,410 --> 00:02:59,000
rightmost eleman yo m yo garanti

60
00:02:59,000 --> 00:03:01,000
yo dwe klase nan plas ki kòrèk yo.

61
00:03:01,000 --> 00:03:02,280
Si ou vle wè sa a pou tèt ou,

62
00:03:02,280 --> 00:03:05,500
nou ka eseye li sou yon lis [9, 6, 5, 3, 2] konplètman bak.

63
00:03:05,500 --> 00:03:08,220
Apre yon sèl pase nan lis la an antye,

64
00:03:08,220 --> 00:03:09,220
[Son nan ekri]

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
eleman nan rightmost 9 se nan plas apwopriye li yo.

67
00:03:21,250 --> 00:03:24,760
Apre dezyèm lan pass-through, 6 a ap gen 'bul-up' yo, vin nan

68
00:03:24,760 --> 00:03:26,220
dezyèm plas rightmost.

69
00:03:26,220 --> 00:03:28,840
Eleman yo de sou bò dwat la - 6 ak 9 - yo pral nan kote ki kòrèk yo

70
00:03:28,840 --> 00:03:30,580
apre de kuvèt yo pass-an premye.

71
00:03:30,580 --> 00:03:32,590
>> Se konsa, ki jan nou ka itilize sa-a optimize algorithm a?

72
00:03:32,590 --> 00:03:34,850
Oke, apre yon iterasyon nan etalaj la

73
00:03:34,850 --> 00:03:37,690
nou pa aktyèlman bezwen tcheke eleman nan rightmost

74
00:03:37,690 --> 00:03:39,200
paske nou konnen li la Ranje.

75
00:03:39,200 --> 00:03:43,050
Apre de itérations, nou konnen pou asire w rightmost de eleman yo ki nan plas li.

76
00:03:43,050 --> 00:03:48,260
Se konsa, an jeneral, apre yo fin itérations k nan etalaj la plen,

77
00:03:48,260 --> 00:03:51,550
tcheke eleman yo k pase a se redondants depi nou konnen

78
00:03:51,550 --> 00:03:52,360
yo ap nan kote ki kòrèk la deja.

79
00:03:52,360 --> 00:03:54,870
>> Se konsa, si w ap Fouye yon etalaj de n eleman,

80
00:03:54,870 --> 00:03:57,870
sou iterasyon nan premye - you'll gen sòt tout nan eleman yo - premye n-0 a.

81
00:03:57,870 --> 00:04:04,170
Sou iterasyon, dezyèm lan, ou pral gen fè yon gade nan tout nan eleman yo, men dènye a -

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

83
00:04:07,090 --> 00:04:10,520
Yon lòt Optimization ta kapab ou tcheke si se lis la deja klase

84
00:04:10,520 --> 00:04:11,710
yo apre chak iterasyon.

85
00:04:11,710 --> 00:04:13,900
Si li la deja klase, nou pa bezwen fè nenpòt ki plis itérations

86
00:04:13,900 --> 00:04:15,310
nan lis la.

87
00:04:15,310 --> 00:04:16,220
Ki jan nou ka fè sa?

88
00:04:16,220 --> 00:04:19,360
Oke, si nou pa fè okenn echanj sou yon pase nan-nan lis la,

89
00:04:19,360 --> 00:04:22,350
li nan klè ki te lis la deja klase paske nou pa t 'swap anyen.

90
00:04:22,350 --> 00:04:24,160
Se konsa, nou definitivman pa bezwen sòt ankò.

91
00:04:24,160 --> 00:04:27,960
>> Petèt ou ta ka inisyalize yon varyab drapo rele 'pa Ranje' yo, vin

92
00:04:27,960 --> 00:04:30,990
fo ak chanje li nan vre si ou gen nenpòt eleman swap sou

93
00:04:30,990 --> 00:04:32,290
yon sèl iterasyon nan etalaj la.

94
00:04:32,290 --> 00:04:35,350
Oswa menm, fè yon kontwa nan konte konbyen echanj ou fè

95
00:04:35,350 --> 00:04:37,040
sou nenpòt ki iterasyon bay yo.

96
00:04:37,040 --> 00:04:40,040
Nan fen yon iterasyon, si ou pa t 'swap nenpòt nan eleman yo,

97
00:04:40,040 --> 00:04:41,780
ou konnen se lis la deja klase epi w ap fè.

98
00:04:41,780 --> 00:04:44,090
Triye jarèt, tankou algoritm klasman lòt, yo ka

99
00:04:44,090 --> 00:04:46,960
tweaked pou travay pou nenpòt eleman ki gen yon metòd kòmande.

100
00:04:46,960 --> 00:04:50,610
>> Sa se, bay de eleman ou gen yon fason yo di si yon sèl nan premye

101
00:04:50,610 --> 00:04:53,770
se pi gran pase, egal a oswa pi piti pase dezyèm lan.

102
00:04:53,770 --> 00:04:56,870
Pou egzanp, ou ta ka klase lèt nan alfabè a lè li di

103
00:04:56,870 --> 00:05:00,520
ke yon <b, b <c, elatriye

104
00:05:00,520 --> 00:05:03,830
Oswa ou ta ka sòt jou nan semèn lan kote Dimanch se mwens pase Lendi

105
00:05:03,830 --> 00:05:05,110
ki se mwens pase Madi.

106
00:05:05,110 --> 00:05:09,630
>> Triye jarèt se pa pa gen okenn vle di yon algorithm klasman trè efikas oswa vit.

107
00:05:09,630 --> 00:05:12,370
Ègzekutabl pi move-ka li se Big O nan n ²

108
00:05:12,370 --> 00:05:14,810
paske ou gen fè n itérations nan yon lis

109
00:05:14,810 --> 00:05:18,430
tcheke tout eleman n chak pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Fwa sa a, kouri vle di ke kòm nimewo a nan eleman ou ap Fouye ogmante,

111
00:05:22,730 --> 00:05:24,330
tan an kouri ogmante quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Men, si efikasite se pa yon pi gwo enkyetid nan pwogram ou an

113
00:05:27,330 --> 00:05:29,550
oswa si w ap sèlman Fouye yon ti kantite eleman,

114
00:05:29,550 --> 00:05:31,660
ou ta ka jwenn Triye Bubble itil paske

115
00:05:31,660 --> 00:05:33,360
li nan youn nan pi senp algoritm yo Fouye yo konprann

116
00:05:33,360 --> 00:05:34,250
ak kòd.

117
00:05:34,250 --> 00:05:37,270
Li la tou yon bon fason jwenn eksperyans avèk tradui yon teyorik

118
00:05:37,270 --> 00:05:40,220
algorithm nan kòd fonksyone vrè.

119
00:05:40,220 --> 00:05:43,000
Oke, sa a, se Triye Bubble pou ou. Mèsi pou gade.

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