1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Rendit flluskoj]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Universitetin e Harvardit]

3
00:00:04,560 --> 00:00:07,500
[KJO ËSHTË CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Rendit Bubble është një shembull i një algoritmi klasifikim -

5
00:00:11,730 --> 00:00:14,460
që është, një procedurë për klasifikim e një sërë elementeve në

6
00:00:14,460 --> 00:00:15,840
ngjitje apo rend zbritës.

7
00:00:15,840 --> 00:00:18,710
Për shembull, në qoftë se ju të kërkuar për të zgjidhur një rrjet i përbërë nga numrat

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], një zbatimi korrekt i Renditur Bubble do të kthejë

9
00:00:23,060 --> 00:00:26,260
grup renditura [2, 3, 5, 9] në ngjitje rendin.

10
00:00:26,260 --> 00:00:28,850
Tani, unë jam duke shkuar për të shpjeguar në pseudokod si algorithm punon.

11
00:00:28,850 --> 00:00:34,000
>> Le të thonë se ne jemi zgjidhja një listë prej 5 integers - 3, 2, 9, 6, dhe 5.

12
00:00:34,000 --> 00:00:37,650
Algorithm fillon duke shikuar në dy elementet e para, 3 dhe 2,

13
00:00:37,650 --> 00:00:40,850
dhe kontrolluar nëse ata janë jashtë rendit të afërm me njëri-tjetrin.

14
00:00:40,850 --> 00:00:43,150
Ata janë - 3 është më i madh se 2.

15
00:00:43,150 --> 00:00:45,190
Të jetë në mënyrë ngjitje, ata duhet të jenë mënyra të tjera përreth.

16
00:00:45,190 --> 00:00:46,610
Pra, ne bie në ujdi tyre.

17
00:00:46,610 --> 00:00:49,760
Tani lista duket si ky: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Tjetra, ne shikojmë në elementet e dytë dhe të tretë, 3 dhe 9.

19
00:00:52,450 --> 00:00:55,770
Ata janë në mënyrë të saktë në lidhje me njëri-tjetrin.

20
00:00:55,770 --> 00:00:58,800
Kjo është, është më pak se 3 9 kështu që algoritmi nuk bie në ujdi tyre.

21
00:00:58,800 --> 00:01:01,900
Tjetra, ne shikojmë në 9 dhe 6. Ata janë jashtë funksionit.

22
00:01:01,900 --> 00:01:04,260
>> Pra, ne duhet të bie në ujdi ato, sepse është më i madh se 9 6.

23
00:01:04,260 --> 00:01:08,840
Së fundi, ne shikojmë në të dy integers fundit, 9 dhe 5.

24
00:01:08,840 --> 00:01:10,850
Ata janë jashtë funksionit, kështu që ata duhet të shkëmbehen.

25
00:01:10,850 --> 00:01:13,360
Pas kalimit të parë nëpër lista e plotë,

26
00:01:13,360 --> 00:01:17,140
ajo duket si kjo: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Jo keq. Është pothuajse e renditura.

28
00:01:19,690 --> 00:01:22,450
Por ne kemi nevojë për të drejtuar nëpër lista për të marrë atë përsëri zgjidhet plotësisht.

29
00:01:22,450 --> 00:01:29,250
Dy është më pak se 3, kështu që ne nuk do të bie në ujdi tyre.

30
00:01:29,250 --> 00:01:31,700
>> Tre është më pak se 6, kështu që ne nuk do të bie në ujdi tyre.

31
00:01:31,700 --> 00:01:35,500
Gjashtë është më i madh se 5. Ne swapped.

32
00:01:35,500 --> 00:01:38,460
Gjashtë është më pak se 9. Ne nuk bie në ujdi.

33
00:01:38,460 --> 00:01:42,170
Pas kalojë përmes dytë, ajo duket si ky: [2, 3, 5, 6, 9]. Përsosur.

34
00:01:42,170 --> 00:01:44,680
Tani, le të shkruajë atë në pseudokod.

35
00:01:44,680 --> 00:01:48,450
Në thelb, për çdo element në listë, ne duhet të shohim në atë

36
00:01:48,450 --> 00:01:50,060
dhe elementi i drejtpërdrejtë në të djathtë të tij.

37
00:01:50,060 --> 00:01:53,420
Nëse ata janë jashtë rendit të afërm me njëri-tjetrin - që është, në qoftë se elementi në të majtë

38
00:01:53,420 --> 00:01:56,810
është më i madh se ai në të djathtë - ne duhet të bie në ujdi dy elemente.

39
00:01:56,810 --> 00:02:01,270
>> Ne e bëjmë këtë për çdo element të listës, dhe ne kemi bërë një të kalojë përmes.

40
00:02:01,270 --> 00:02:05,160
Tani ne vetëm duhet të bëni të kalojë përmes-herë të mjaftueshme për të siguruar listën

41
00:02:05,160 --> 00:02:06,480
është plotësisht, të renditura siç duhet.

42
00:02:06,480 --> 00:02:08,889
Por sa herë nuk kemi të duhet të kalojnë nëpër lista për të

43
00:02:08,889 --> 00:02:10,400
garantoj se ne jemi duke bërë?

44
00:02:10,400 --> 00:02:14,730
E pra, rastin më të keq është nëse ne kemi një listë plotësisht prapa.

45
00:02:14,730 --> 00:02:17,840
Pastaj ajo merr një numër të kalojnë-throughs barabartë me numrin

46
00:02:17,840 --> 00:02:19,730
i elementeve n-1.

47
00:02:19,730 --> 00:02:24,720
Nëse kjo nuk ka kuptim intuitive, të mendojnë për një rast të thjeshtë - lista [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Kjo do të marrë një të kalojë nëpër-për të zgjidhur saktë.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Rasti më i keq është se me 3 elemente të renditura prapa,

50
00:02:33,060 --> 00:02:34,830
ajo do të marrë 2 iterations për të zgjidhur.

51
00:02:34,830 --> 00:02:37,980
Pas një përsëritje, ajo është [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Rendimentet dyta array renditura [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Pra, ju e dini që ju nuk duhet të kalojnë nëpër rrjet, në përgjithësi,

54
00:02:43,350 --> 00:02:46,790
më shumë se n-1 herë, ku n është numri i elementeve në vektorit.

55
00:02:47,090 --> 00:02:50,470
Ajo që quhet Rendit Bubble sepse elementet më të mëdha kanë tendencë për të "flluskë-up '

56
00:02:50,470 --> 00:02:51,950
në të djathtë shumë shpejt.

57
00:02:51,950 --> 00:02:53,980
Në fakt, ky algoritëm ka sjellje shumë interesante.

58
00:02:53,980 --> 00:02:57,410
>> Pas iterations m përmes grup të tërë,

59
00:02:57,410 --> 00:02:59,000
elementet rightmost m janë të garantuara

60
00:02:59,000 --> 00:03:01,000
të zgjidhet në vendin e tyre të saktë.

61
00:03:01,000 --> 00:03:02,280
Nëse ju doni të shihni këtë për veten tuaj,

62
00:03:02,280 --> 00:03:05,500
ne mund ta provoni atë në një listë të plotë prapa [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Pas një të kalojë nëpër gjithë listën,

64
00:03:08,220 --> 00:03:09,220
[Të shëndoshë e të shkruarit]

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
elementi rightmost 9 është në vendin e vet të duhur.

67
00:03:21,250 --> 00:03:24,760
Pasi e dytë të kalojë nëpër-, 6 do të ketë 'bubbled-up' të

68
00:03:24,760 --> 00:03:26,220
Vendin e dytë rightmost.

69
00:03:26,220 --> 00:03:28,840
Dy elementet në të djathtë - 6 dhe 9 - do të jenë në vendet e tyre të saktë

70
00:03:28,840 --> 00:03:30,580
pas para dy Pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Pra, si mund të përdorni këtë për të optimizuar algorithm?

72
00:03:32,590 --> 00:03:34,850
E pra, pas një përsëritje nëpërmjet rrjet

73
00:03:34,850 --> 00:03:37,690
ne nuk të vërtetë nevojë për të kontrolluar elementin rightmost

74
00:03:37,690 --> 00:03:39,200
sepse ne e dimë se është renditura.

75
00:03:39,200 --> 00:03:43,050
Pas dy iterations, ne e dimë për të siguruar rightmost dy elemente janë në vend.

76
00:03:43,050 --> 00:03:48,260
Pra, në përgjithësi, pasi iterations k përmes koleksion të plotë,

77
00:03:48,260 --> 00:03:51,550
kontrolluar elementet e fundit k është i tepërt pasi ne e dimë

78
00:03:51,550 --> 00:03:52,360
ata janë në vendin e saktë tashmë.

79
00:03:52,360 --> 00:03:54,870
>> Pra, nëse ju jeni zgjidhja një sërë elementesh n,

80
00:03:54,870 --> 00:03:57,870
në përsëritje parë - you'll keni për të zgjidhur të gjitha elementet - e parë n-0.

81
00:03:57,870 --> 00:04:04,170
Në përsëritje të dytë, ju do të duhet të shikojmë në të gjitha elementet, por e fundit -

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

83
00:04:07,090 --> 00:04:10,520
Një tjetër optimization mund të jetë për të kontrolluar nëse lista është renditur tashmë

84
00:04:10,520 --> 00:04:11,710
pas çdo përsëritje.

85
00:04:11,710 --> 00:04:13,900
Nëse është e renditur tashmë, ne nuk kemi nevojë për të bërë ndonjë iterations më shumë

86
00:04:13,900 --> 00:04:15,310
nëpër lista.

87
00:04:15,310 --> 00:04:16,220
Si mund ta bëjë këtë?

88
00:04:16,220 --> 00:04:19,360
E pra, në qoftë se ne nuk do të bëjë ndonjë këmbime në një të kalojë nëpër-i listës,

89
00:04:19,360 --> 00:04:22,350
është e qartë se lista u renditur tashmë, sepse nuk kemi asgjë të bie në ujdi.

90
00:04:22,350 --> 00:04:24,160
Pra, ne definitivisht nuk kanë për të zgjidhur përsëri.

91
00:04:24,160 --> 00:04:27,960
>> Ndoshta ju mund të nisja një ndryshore të quajtur flamur 'nuk zgjidhet' për të

92
00:04:27,960 --> 00:04:30,990
rreme dhe për të ndryshuar atë për të vërtetë në qoftë se ju keni të bie në ujdi ndonjë elementet në

93
00:04:30,990 --> 00:04:32,290
një përsëritje nëpër rrjet.

94
00:04:32,290 --> 00:04:35,350
Apo të ngjashme, të bëjë një kundër për të numëruar sa këmbime të bëni

95
00:04:35,350 --> 00:04:37,040
në çdo përsëritje të dhënë.

96
00:04:37,040 --> 00:04:40,040
Në fund të një përsëritje, në qoftë se ju nuk e keni të bie në ujdi ndonjë prej elementeve,

97
00:04:40,040 --> 00:04:41,780
ju e dini listë është renditur tashmë dhe ju jeni bërë.

98
00:04:41,780 --> 00:04:44,090
Rendit Bubble, si algoritme zgjidhja e tjera, mund të jetë

99
00:04:44,090 --> 00:04:46,960
tweaked për të punuar për ndonjë elemente të cilat kanë një metodë urdhërimin.

100
00:04:46,960 --> 00:04:50,610
>> Kjo është, duke pasur parasysh dy elementë që ju keni një mënyrë për të thënë nëse pari

101
00:04:50,610 --> 00:04:53,770
është më e madhe se, ose të barabartë me më pak se dytë.

102
00:04:53,770 --> 00:04:56,870
Për shembull, ju mund të lloj shkronja të alfabetit duke thënë

103
00:04:56,870 --> 00:05:00,520
se a <b, b <c, etj

104
00:05:00,520 --> 00:05:03,830
Ose ju mund të lloj ditë të javës, ku e diela është më pak se e hëna

105
00:05:03,830 --> 00:05:05,110
cila është më pak se martën.

106
00:05:05,110 --> 00:05:09,630
>> Rendit Bubble nuk është aspak një algoritmi shumë efikase ose të shpejtë klasifikim.

107
00:05:09,630 --> 00:05:12,370
Runtime të keq rasti i tij është Big O ² n

108
00:05:12,370 --> 00:05:14,810
sepse ju keni për të bërë iterations n përmes një listë

109
00:05:14,810 --> 00:05:18,430
kontrolluar të gjitha elementet n njëri-kalojë nëpër, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Këtë herë do të thotë që të kandidojë si numri i elementeve që ju jeni klasifikim rritje,

111
00:05:22,730 --> 00:05:24,330
Ora drejtuar rrit quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Por në qoftë se efikasiteti nuk është një shqetësim i madh i programit tuaj

113
00:05:27,330 --> 00:05:29,550
ose në qoftë se ju jeni vetëm zgjidhja një numër të vogël të elementeve,

114
00:05:29,550 --> 00:05:31,660
ju mund të gjeni të dobishme për shkak se Rendit Bubble

115
00:05:31,660 --> 00:05:33,360
kjo është një nga algoritme të thjeshtë për të kuptuar klasifikim

116
00:05:33,360 --> 00:05:34,250
dhe për kodin.

117
00:05:34,250 --> 00:05:37,270
Kjo është gjithashtu një mënyrë e madhe për të marrë përvojë me përkthimin e një teorike

118
00:05:37,270 --> 00:05:40,220
algorithm në kodin aktual funksional.

119
00:05:40,220 --> 00:05:43,000
E pra, kjo është Rendit flluskë për ju. Faleminderit për shikimin.

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