1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Sort bubble]

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

3
00:00:04,560 --> 00:00:07,500
[B'DAN QIEGĦED CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Sort Bubble huwa eżempju ta 'algoritmu issortjar -

5
00:00:11,730 --> 00:00:14,460
jiġifieri, proċedura għall-għażla ta 'sett ta' elementi fil-

6
00:00:14,460 --> 00:00:15,840
axxendenti jew dixxendenti ordni.

7
00:00:15,840 --> 00:00:18,710
Per eżempju, jekk inti riedu biex issolvi firxa magħmul min-numri

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], implimentazzjoni korretta ta 'Sort Bubble se jerġa' lura l-

9
00:00:23,060 --> 00:00:26,260
firxa magħżula [2, 3, 5, 9] f'ordni axxendenti.

10
00:00:26,260 --> 00:00:28,850
Issa, jien ser jispjegaw fil pseudocode kif l-algoritmu xogħlijiet.

11
00:00:28,850 --> 00:00:34,000
>> Ejja ngħidu aħna qed issortjar lista ta '5 numri interi - 3, 2, 9, 6, u 5.

12
00:00:34,000 --> 00:00:37,650
L-algoritmu jibda billi tħares lejn l-ewwel żewġ elementi, 3 u 2,

13
00:00:37,650 --> 00:00:40,850
u l-iċċekkjar jekk dawn qed out of order relattivi għal xulxin.

14
00:00:40,850 --> 00:00:43,150
Dawn huma - 3 huwa akbar minn 2.

15
00:00:43,150 --> 00:00:45,190
Biex tkun sabiex axxendenti, dawn għandhom ikunu l-mod ieħor madwar.

16
00:00:45,190 --> 00:00:46,610
Għalhekk, aħna tpartit minnhom.

17
00:00:46,610 --> 00:00:49,760
Issa l-lista tidher bħal dan: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Sussegwentement, inħarsu lejn l-elementi tieni u t-tielet subparagrafi, 3 u 9.

19
00:00:52,450 --> 00:00:55,770
Huma qed fl-ordni korretta relattivi għal xulxin.

20
00:00:55,770 --> 00:00:58,800
Dan huwa, 3 huwa anqas minn 9 hekk l-algoritmu ma tpartit minnhom.

21
00:00:58,800 --> 00:01:01,900
Sussegwentement, aħna nħarsu lejn 9 u 6. Huma qed out of order.

22
00:01:01,900 --> 00:01:04,260
>> Għalhekk, għandna bżonn li tpartit lilhom minħabba 9 huwa akbar minn 6.

23
00:01:04,260 --> 00:01:08,840
Fl-aħħar nett, irridu nħarsu lejn l-aħħar żewġ interi, 9 u 5.

24
00:01:08,840 --> 00:01:10,850
Huma qed out of order, sabiex dawn għandhom jiġu skambjati.

25
00:01:10,850 --> 00:01:13,360
Wara l-pass kompleta ewwel permezz tal-lista,

26
00:01:13,360 --> 00:01:17,140
jidher qisu dan: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Mhux ħażin. Huwa kważi magħżula.

28
00:01:19,690 --> 00:01:22,450
Iżda għandna bżonn li tgħaddi minn ġos-lista mill-ġdid biex tiksbu kompletament magħżula.

29
00:01:22,450 --> 00:01:29,250
Żewġ huwa inqas minn 3, hekk aħna ma tpartit minnhom.

30
00:01:29,250 --> 00:01:31,700
>> Tliet huwa inqas minn 6, hekk aħna ma tpartit minnhom.

31
00:01:31,700 --> 00:01:35,500
Sitta huwa ikbar minn 5. Aħna biddlu.

32
00:01:35,500 --> 00:01:38,460
Sitta huwa inqas minn 9. Aħna ma tpartit.

33
00:01:38,460 --> 00:01:42,170
Wara t-tieni pass permezz ta ', jidher qisu dan: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Issa, ejja tikteb dan fl pseudocode.

35
00:01:44,680 --> 00:01:48,450
Bażikament, għal kull element fil-lista, għandna bżonn li nħarsu lejn din

36
00:01:48,450 --> 00:01:50,060
u l-element direttament għad-dritt tiegħu.

37
00:01:50,060 --> 00:01:53,420
Jekk huma barra mill-ordni relattiva għal xulxin - jiġifieri, jekk l-element fuq ix-xellug

38
00:01:53,420 --> 00:01:56,810
huwa akbar mill-wieħed fuq il-lemin - għandna tpartit iż-żewġ elementi.

39
00:01:56,810 --> 00:02:01,270
>> Aħna nagħmlu dan għal kull element tal-lista, u aħna ħadna wieħed jgħaddi permezz.

40
00:02:01,270 --> 00:02:05,160
Issa aħna biss għandhom jagħmlu l-ħinijiet pass-through biżżejjed biex jiżguraw il-lista

41
00:02:05,160 --> 00:02:06,480
hija kompletament, magħżul b'mod xieraq.

42
00:02:06,480 --> 00:02:08,889
Imma kif ħafna drabi għandna biex jgħaddu l-lista biex

43
00:02:08,889 --> 00:02:10,400
garanzija li aħna qed isir?

44
00:02:10,400 --> 00:02:14,730
Ukoll, ix-xenarju tal-agħar każ hija jekk għandna lista kompletament lura.

45
00:02:14,730 --> 00:02:17,840
Imbagħad, hija tieħu numru ta 'jgħaddi throughs ugwali għan-numru

46
00:02:17,840 --> 00:02:19,730
ta 'elementi n-1.

47
00:02:19,730 --> 00:02:24,720
Jekk dan ma jagħmilx sens intuwittivament, think ta 'każ sempliċi - il-lista [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Dan ser jieħu waħda pass-through li sort korrett.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - L-agħar każ hija li bi 3 elementi magħżula lura,

50
00:02:33,060 --> 00:02:34,830
li għaddej biex tieħu 2 iterazzjonijiet biex sort.

51
00:02:34,830 --> 00:02:37,980
Wara iterazzjoni waħda, huwa [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Il-rendimenti 2-firxa magħżula [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Allura inti taf li inti qatt ma jkollhom jgħaddu mill-firxa, b'mod ġenerali,

54
00:02:43,350 --> 00:02:46,790
aktar minn n-1 drabi, meta n hija n-numru ta 'elementi fil-firxa.

55
00:02:47,090 --> 00:02:50,470
Huwa sejjaħ Sort Bubble minħabba li l-elementi akbar tendenza li "bużżieqa up"

56
00:02:50,470 --> 00:02:51,950
lejn il-lemin pretty malajr.

57
00:02:51,950 --> 00:02:53,980
Fil-fatt, dan algoritmu għandha imġiba interessanti ħafna.

58
00:02:53,980 --> 00:02:57,410
>> Wara iterazzjonijiet m permezz tal-firxa sħiħa,

59
00:02:57,410 --> 00:02:59,000
l-elementi m lemini huma garantiti

60
00:02:59,000 --> 00:03:01,000
li jintgħażlu fi post korretta tagħhom.

61
00:03:01,000 --> 00:03:02,280
Jekk inti tixtieq li tara dan għalik innifsek,

62
00:03:02,280 --> 00:03:05,500
nistgħu tipprova fuq lista kompletament lura [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Wara jgħaddu l-lista sħiħa,

64
00:03:08,220 --> 00:03:09,220
[Ħoss tal-kitba]

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
l-element lemini 9 huwa fil-post xieraq tagħha.

67
00:03:21,250 --> 00:03:24,760
Wara t-tieni pass-through, il-6 se jkollu "effervexxentement up" għall-

68
00:03:24,760 --> 00:03:26,220
post lemini 2.

69
00:03:26,220 --> 00:03:28,840
Iż-żewġ elementi fuq id-dritt - 6 u 9 - se jkunu fil-postijiet korretta tagħhom

70
00:03:28,840 --> 00:03:30,580
wara l-ewwel żewġ jgħaddu throughs.

71
00:03:30,580 --> 00:03:32,590
>> Allura, kif nistgħu jużaw dan biex jottimizzaw l-algoritmu?

72
00:03:32,590 --> 00:03:34,850
Ukoll, wara iterazzjoni waħda mill-firxa

73
00:03:34,850 --> 00:03:37,690
aħna ma attwalment bżonn li jiċċekkja l-element lemini

74
00:03:37,690 --> 00:03:39,200
għaliex nafu dan huwa magħżula.

75
00:03:39,200 --> 00:03:43,050
Wara żewġ iterazzjonijiet, nafu fiċ-ċert l-lemini żewġ elementi huma fis-seħħ.

76
00:03:43,050 --> 00:03:48,260
Għalhekk, b'mod ġenerali, wara iterazzjonijiet k permezz tal-firxa sħiħa,

77
00:03:48,260 --> 00:03:51,550
kontroll tal-elementi k aħħar hija żejda peress li nafu

78
00:03:51,550 --> 00:03:52,360
dawn qed fil-post korretta diġà.

79
00:03:52,360 --> 00:03:54,870
>> Mela jekk int issortjar firxa ta 'elementi n,

80
00:03:54,870 --> 00:03:57,870
fuq l-ewwel iterazzjoni - you'll jkollhom biex issolvi l-elementi kollha - l-ewwel n-0.

81
00:03:57,870 --> 00:04:04,170
Fuq il-tieni iterazzjoni, inti ser ikollok tħares lejn l-elementi kollha, iżda l-aħħar -

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

83
00:04:07,090 --> 00:04:10,520
Ieħor ottimizzazzjoni tista 'tkun li jiċċekkjaw jekk il-lista hija diġà magħżula

84
00:04:10,520 --> 00:04:11,710
wara kull iterazzjoni.

85
00:04:11,710 --> 00:04:13,900
Jekk huwa diġà magħżula, ma kellniex bżonn tagħmel iterazzjonijiet kwalunkwe aktar

86
00:04:13,900 --> 00:04:15,310
permezz tal-lista.

87
00:04:15,310 --> 00:04:16,220
Kif nistgħu nagħmlu dan?

88
00:04:16,220 --> 00:04:19,360
Ukoll, jekk aħna ma tagħmel l-ebda swaps fuq pass-through tal-lista,

89
00:04:19,360 --> 00:04:22,350
huwa ċar li l-lista kienet diġà magħżula għaliex aħna ma tpartit xejn.

90
00:04:22,350 --> 00:04:24,160
Allura aħna żgur ma jkollhom sort mill-ġdid.

91
00:04:24,160 --> 00:04:27,960
>> Forsi inti tista 'initialize varjabbli bandiera imsejjaħ "ma jintgħażlux" li

92
00:04:27,960 --> 00:04:30,990
falza u bidla li minnu jekk inti għandek tpartit xi elementi dwar

93
00:04:30,990 --> 00:04:32,290
iterazzjoni waħda mill-firxa.

94
00:04:32,290 --> 00:04:35,350
Jew bl-istess mod, jagħmel kontro biex jingħaddu kemm swaps inti tagħmel

95
00:04:35,350 --> 00:04:37,040
fuq kull iterazzjoni partikolari.

96
00:04:37,040 --> 00:04:40,040
Fl-aħħar ta 'iterazzjoni, jekk inti ma tpartit ebda mill-elementi,

97
00:04:40,040 --> 00:04:41,780
inti taf l-lista hija diġà magħżula u qed isir.

98
00:04:41,780 --> 00:04:44,090
Sort Bubble, bħal algoritmi issortjar oħra, jista 'jkun

99
00:04:44,090 --> 00:04:46,960
tweaked li jaħdmu għal elementi li għandhom metodu tordna.

100
00:04:46,960 --> 00:04:50,610
>> Dan huwa, minħabba żewġ elementi ikollok mod biex jgħidu jekk l-ewwel waħda

101
00:04:50,610 --> 00:04:53,770
huwa akbar minn, ugwali għal jew inqas mill-2.

102
00:04:53,770 --> 00:04:56,870
Per eżempju, inti tista sort ittri tal-alfabett billi qal

103
00:04:56,870 --> 00:05:00,520
li <b, b <c, eċċ

104
00:05:00,520 --> 00:05:03,830
Jew inti tista sort ġranet tal-ġimgħa fejn Ħadd hija inqas minn it-tnejn

105
00:05:03,830 --> 00:05:05,110
li hija inqas minn Tlieta.

106
00:05:05,110 --> 00:05:09,630
>> Sort Bubble huwa bl-ebda mod algoritmu issortjar effiċjenti ħafna jew malajr.

107
00:05:09,630 --> 00:05:12,370
Agħar każ runtime tagħha hija Big O ta 'n ²

108
00:05:12,370 --> 00:05:14,810
għaliex inti għandek tagħmel iterazzjonijiet n permezz ta 'lista

109
00:05:14,810 --> 00:05:18,430
iċċekkjar elementi kollha n kull pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Din id-darba run ifisser li bħala n-numru ta 'elementi int issortjar żidiet,

111
00:05:22,730 --> 00:05:24,330
il-ħin ta 'tħaddim żidiet quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Imma jekk effiċjenza mhuwiex ta 'tħassib kbir tal-programm tiegħek

113
00:05:27,330 --> 00:05:29,550
jew jekk int biss issortjar numru żgħir ta 'elementi,

114
00:05:29,550 --> 00:05:31,660
inti tista 'ssib Sort Bubble utli għaliex

115
00:05:31,660 --> 00:05:33,360
huwa wieħed mill-algoritmi sempliċi għażla li wieħed jifhem

116
00:05:33,360 --> 00:05:34,250
u għall-kodiċi.

117
00:05:34,250 --> 00:05:37,270
Huwa wkoll mod tajjeb ħafna biex jiksbu esperjenza ma jittraduċu teoretiku

118
00:05:37,270 --> 00:05:40,220
algoritmu fis-kodiċi funzjonament attwali.

119
00:05:40,220 --> 00:05:43,000
Ukoll, li Sort Bubble għalik. Grazzi għall-ħars.

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