1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [SORT swigen]

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

3
00:00:04,560 --> 00:00:07,500
[HWN YW CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Trefnu yn Bubble yn enghraifft o algorithm didoli -

5
00:00:11,730 --> 00:00:14,460
hynny yw, gweithdrefn ar gyfer didoli set o elfennau mewn

6
00:00:14,460 --> 00:00:15,840
trefn esgynnol neu ddisgynnol.

7
00:00:15,840 --> 00:00:18,710
Er enghraifft, os ydych am roi trefn ar amrywiaeth sy'n cynnwys y rhifau

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], byddai gweithredu cywir Trefnu yn Bubble dychwelyd y

9
00:00:23,060 --> 00:00:26,260
amrywiaeth didoli [2, 3, 5, 9] yn nhrefn esgynnol.

10
00:00:26,260 --> 00:00:28,850
Nawr, dw i'n mynd i egluro mewn pseudocode sut y mae'r algorithm yn gweithio.

11
00:00:28,850 --> 00:00:34,000
>> Lets 'ddeud ein bod yn didoli rhestr o 5 cyfanrifau - 3, 2, 9, 6, a 5.

12
00:00:34,000 --> 00:00:37,650
Mae'r algorithm yn dechrau drwy edrych ar y ddwy elfen gyntaf, 3 a 2,

13
00:00:37,650 --> 00:00:40,850
a gwirio os ydynt yn allan o drefn mewn perthynas â'i gilydd.

14
00:00:40,850 --> 00:00:43,150
Maent yn - 3 yn fwy na 2.

15
00:00:43,150 --> 00:00:45,190
I fod er mwyn esgynnol, dylent fod yn ffordd arall o gwmpas.

16
00:00:45,190 --> 00:00:46,610
Felly, rydym yn eu cyfnewid.

17
00:00:46,610 --> 00:00:49,760
Nawr bod y rhestr yn edrych fel hyn: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Nesaf, byddwn yn edrych ar yr elfennau ail a'r drydedd, 3 a 9.

19
00:00:52,450 --> 00:00:55,770
Maen nhw yn y drefn gywir mewn perthynas â'i gilydd.

20
00:00:55,770 --> 00:00:58,800
Hynny yw, 3 yn llai na 9 fel nad yw'r algorithm yn eu cyfnewid.

21
00:00:58,800 --> 00:01:01,900
Nesaf, byddwn yn edrych ar 9 a 6. Maen nhw'n allan o drefn.

22
00:01:01,900 --> 00:01:04,260
>> Felly, mae angen i ni eu cyfnewid am 9 yn fwy na 6.

23
00:01:04,260 --> 00:01:08,840
Yn olaf, rydym yn edrych ar y ddau olaf cyfanrifau, 9 a 5.

24
00:01:08,840 --> 00:01:10,850
Maen nhw'n allan o drefn, felly mae'n rhaid iddynt gael eu cyfnewid.

25
00:01:10,850 --> 00:01:13,360
Ar ôl y tocyn cyflawn cyntaf drwy'r rhestr,

26
00:01:13,360 --> 00:01:17,140
mae'n edrych fel hyn: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Ddim yn ddrwg. Mae'n datrys bron.

28
00:01:19,690 --> 00:01:22,450
Ond mae angen i redeg drwy'r rhestr eto i gael ei datrys yn llwyr.

29
00:01:22,450 --> 00:01:29,250
Dau yn llai na 3, felly nid ydym yn eu cyfnewid.

30
00:01:29,250 --> 00:01:31,700
>> Tri yn llai na 6, felly nid ydym yn eu cyfnewid.

31
00:01:31,700 --> 00:01:35,500
Chwech yn fwy na 5. Rydym yn cyfnewid.

32
00:01:35,500 --> 00:01:38,460
Chwech yn llai na 9. Nid ydym yn cyfnewid.

33
00:01:38,460 --> 00:01:42,170
Ar ôl yr Ail drwy basio, mae'n edrych fel hyn: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nawr, gadewch i ni ysgrifennu yn pseudocode.

35
00:01:44,680 --> 00:01:48,450
Yn y bôn, ar gyfer pob elfen yn y rhestr, mae angen i ni edrych arno

36
00:01:48,450 --> 00:01:50,060
a'r elfen uniongyrchol i'w dde.

37
00:01:50,060 --> 00:01:53,420
Os ydynt yn allan o drefn mewn perthynas â'i gilydd - hynny yw, os yw'r elfen ar y chwith

38
00:01:53,420 --> 00:01:56,810
yn fwy na'r un ar y dde - dylem gyfnewid y ddwy elfen.

39
00:01:56,810 --> 00:02:01,270
>> Rydym yn gwneud hyn ar gyfer pob elfen o'r rhestr, ac rydym wedi gwneud un pasio drwodd.

40
00:02:01,270 --> 00:02:05,160
Nawr rydym yn unig rhaid i ni wneud yr amseroedd pasio drwy ddigon i sicrhau bod y rhestr

41
00:02:05,160 --> 00:02:06,480
yn llawn, didoli yn gywir.

42
00:02:06,480 --> 00:02:08,889
Ond faint o weithiau rhaid i ni fynd trwy'r rhestr i

43
00:02:08,889 --> 00:02:10,400
gwarantu ein bod yn ei wneud?

44
00:02:10,400 --> 00:02:14,730
Wel, y senario gwaethaf-achos os oes gennym restr cwbl yn ôl.

45
00:02:14,730 --> 00:02:17,840
Yna mae'n cymryd nifer o basio-throughs hafal i'r nifer

46
00:02:17,840 --> 00:02:19,730
o elfennau n-1.

47
00:02:19,730 --> 00:02:24,720
Os nad yw hyn yn gwneud synnwyr yn reddfol, meddyliwch am achos syml - mae'r rhestr [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Mae hyn yn mynd i gymryd un pasio trwodd i ddidoli yn gywir.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Yr achos gwaethaf yw bod â 3 elfen didoli yn ôl,

50
00:02:33,060 --> 00:02:34,830
mae'n mynd i fynd â 2 iteriadau i ddidoli.

51
00:02:34,830 --> 00:02:37,980
Ar ôl un fersiwn, mae'n [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Mae'r cynnyrch ail casgliad didoli [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Felly, rydych yn gwybod eich bod byth yn rhaid i chi fynd trwy'r casgliad, yn gyffredinol,

54
00:02:43,350 --> 00:02:46,790
mwy na n-1 gwaith, lle mae n yn nifer o elfennau yn y rhesi.

55
00:02:47,090 --> 00:02:50,470
Mae'n cael ei alw Trefnu yn Bubble oherwydd bod yr elfennau mwyaf yn tueddu i 'swigen-up'

56
00:02:50,470 --> 00:02:51,950
i'r dde yn weddol gyflym.

57
00:02:51,950 --> 00:02:53,980
Mewn gwirionedd, mae hyn yn algorithm wedi ymddwyn yn ddiddorol iawn.

58
00:02:53,980 --> 00:02:57,410
>> Ar ôl fersiynau m trwy'r amrywiaeth gyfan,

59
00:02:57,410 --> 00:02:59,000
yr elfennau m rightmost yn cael eu gwarantu

60
00:02:59,000 --> 00:03:01,000
i gael eu didoli yn eu lle cywir.

61
00:03:01,000 --> 00:03:02,280
Os ydych chi eisiau gweld hyn drosoch eich hun,

62
00:03:02,280 --> 00:03:05,500
gallwn geisio ar restr gwbl yn ôl [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Ar ôl un llwyddiant drwy'r rhestr gyfan,

64
00:03:08,220 --> 00:03:09,220
[Gadarn o ysgrifennu]

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
yr elfen rightmost 9 yw yn ei le priodol.

67
00:03:21,250 --> 00:03:24,760
Ar ôl yr ail pasio drwy, bydd y 6 wedi 'bubbled-fyny' i'r

68
00:03:24,760 --> 00:03:26,220
yn ail rightmost.

69
00:03:26,220 --> 00:03:28,840
Mae'r ddwy elfen ar y dde - 6 a 9 - bydd yn eu llefydd cywir

70
00:03:28,840 --> 00:03:30,580
ar ôl y ddau gyntaf pasio-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Felly, sut gallwn ddefnyddio hyn i wneud y gorau o algorithm?

72
00:03:32,590 --> 00:03:34,850
Wel, ar ôl un fersiwn trwy'r amrywiaeth

73
00:03:34,850 --> 00:03:37,690
dydyn ni ddim yn angen i chi wirio'r elfen rightmost

74
00:03:37,690 --> 00:03:39,200
oherwydd rydym yn gwybod ei fod yn datrys.

75
00:03:39,200 --> 00:03:43,050
Ar ôl ddau gylch, rydym yn gwybod yn sicr y ddwy rightmost elfennau yn eu lle.

76
00:03:43,050 --> 00:03:48,260
Felly, yn gyffredinol, ar ôl fersiynau k drwy'r amrywiaeth lawn,

77
00:03:48,260 --> 00:03:51,550
gwirio elfennau k olaf yn ddiangen gan ein bod yn gwybod

78
00:03:51,550 --> 00:03:52,360
eu bod yn y lleoliad cywir yn barod.

79
00:03:52,360 --> 00:03:54,870
>> Felly, os ydych yn didoli amrywiaeth o elfennau n,

80
00:03:54,870 --> 00:03:57,870
ar y fersiwn cyntaf - you'll rhaid i ni drefnu pob un o'r elfennau - y cyntaf n-0.

81
00:03:57,870 --> 00:04:04,170
Ar yr ail ailadroddiad, bydd rhaid i chi edrych ar yr holl elfennau, ond yr olaf -

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

83
00:04:07,090 --> 00:04:10,520
Arall efallai optimization fydd gwneud yn siwr os bydd y rhestr yn cael ei datrys eisoes

84
00:04:10,520 --> 00:04:11,710
ar ôl pob iteriad.

85
00:04:11,710 --> 00:04:13,900
Os yw'n datrys eisoes, nid oes angen i ni wneud mwy o iteriadau

86
00:04:13,900 --> 00:04:15,310
drwy'r rhestr.

87
00:04:15,310 --> 00:04:16,220
Sut allwn ni wneud hyn?

88
00:04:16,220 --> 00:04:19,360
Wel, os nad ydym yn gwneud unrhyw cyfnewid ar sail pasio trwodd y rhestr,

89
00:04:19,360 --> 00:04:22,350
mae'n amlwg bod y rhestr yn cael ei datrys eisoes oherwydd nad oeddem yn cyfnewid unrhyw beth.

90
00:04:22,350 --> 00:04:24,160
Felly, rydym yn bendant yn rhaid i ddatrys eto.

91
00:04:24,160 --> 00:04:27,960
>> Efallai y gallech ymgychwyn newidyn baner o'r enw 'ddim yn datrys' i

92
00:04:27,960 --> 00:04:30,990
anwir a chyfnewid 'i at wir os oes rhaid i gyfnewid unrhyw elfennau ar

93
00:04:30,990 --> 00:04:32,290
1 ailadrodd drwy'r casgliad.

94
00:04:32,290 --> 00:04:35,350
Neu yn yr un modd, gwnewch yn groes i gyfrif faint o gyfnewid rydych yn gwneud

95
00:04:35,350 --> 00:04:37,040
ar unrhyw fersiwn a roddwyd.

96
00:04:37,040 --> 00:04:40,040
Ar ddiwedd iteriad, os nad ydych wedi cyfnewid unrhyw un o'r elfennau,

97
00:04:40,040 --> 00:04:41,780
eich bod yn gwybod y rhestr yn cael ei datrys eisoes ac rydych chi wedi gorffen.

98
00:04:41,780 --> 00:04:44,090
Trefnu yn Bubble, fel algorithmau didoli eraill, fod yn

99
00:04:44,090 --> 00:04:46,960
tweaked i weithio i unrhyw elfennau sy'n cael dull archebu.

100
00:04:46,960 --> 00:04:50,610
>> Hynny yw, o ystyried dwy elfen gennych ffordd i ddweud os yw'r un cyntaf

101
00:04:50,610 --> 00:04:53,770
yn fwy na, hafal i neu'n llai na'r ail.

102
00:04:53,770 --> 00:04:56,870
Er enghraifft, gallech roi trefn ar lythrennau'r wyddor drwy ddweud

103
00:04:56,870 --> 00:05:00,520
bod a <b, b <c, ac ati

104
00:05:00,520 --> 00:05:03,830
Neu gallech roi trefn ar ddiwrnod o'r wythnos lle mae Sul yn llai na Dydd Llun

105
00:05:03,830 --> 00:05:05,110
sy'n llai na dydd Mawrth.

106
00:05:05,110 --> 00:05:09,630
>> Trefnu yn Bubble nid yw algorithm didoli effeithlon iawn neu gyflym.

107
00:05:09,630 --> 00:05:12,370
Mae ei gwaethaf runtime yn Big O o n ²

108
00:05:12,370 --> 00:05:14,810
oherwydd bod yn rhaid i chi wneud iteriadau n trwy restr

109
00:05:14,810 --> 00:05:18,430
gwirio holl elfennau n bob pasio drwy, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Y tro hwn ei redeg yn golygu fod y nifer o elfennau ydych yn didoli yn cynyddu,

111
00:05:22,730 --> 00:05:24,330
yr amser yn rhedeg yn cynyddu quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Ond os nad yw effeithlonrwydd yn bryder mawr o'ch rhaglen

113
00:05:27,330 --> 00:05:29,550
neu os ydych ond yn didoli nifer fach o elfennau,

114
00:05:29,550 --> 00:05:31,660
efallai y byddwch yn dod o hyd i Trefnu yn Bubble ddefnyddiol oherwydd

115
00:05:31,660 --> 00:05:33,360
mae'n un o'r algorithmau symlaf didoli i ddeall

116
00:05:33,360 --> 00:05:34,250
ac i cod.

117
00:05:34,250 --> 00:05:37,270
Mae hefyd yn ffordd wych o gael profiad gyda gyfieithu a damcaniaethol

118
00:05:37,270 --> 00:05:40,220
algorithm i mewn i god gweithredu gwirioneddol.

119
00:05:40,220 --> 00:05:43,000
Wel, dyna Trefnu yn Bubble i chi. Diolch am wylio.

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