1
00:00:00,000 --> 00:00:03,360
>> [Daqq tal-mużika]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Kull dritt, hekk
sort bużżieqa huwa algoritmu

4
00:00:06,730 --> 00:00:08,730
inti tista 'tuża biex issolvi sett ta' elementi.

5
00:00:08,730 --> 00:00:10,850
Ejja tagħti ħarsa lejn kif taħdem.

6
00:00:10,850 --> 00:00:13,240
>> Allura l-idea bażika wara
sort bużżieqa hija din.

7
00:00:13,240 --> 00:00:17,340
Aħna ġeneralment jridux jimxu ogħla
elementi vvalutati ġeneralment fuq il-lemin,

8
00:00:17,340 --> 00:00:20,340
u t'isfel elementi vvalutati ġeneralment
lejn ix-xellug, kif nistgħu nistennew.

9
00:00:20,340 --> 00:00:23,256
Aħna rridu l-affarijiet aktar baxxi li tkun fil
il-bidu, u l-affarijiet ogħla

10
00:00:23,256 --> 00:00:24,970
li jkun fl-aħħar.

11
00:00:24,970 --> 00:00:26,130
>> Kif nistgħu nagħmlu dan?

12
00:00:26,130 --> 00:00:28,040
Ukoll fil-kodiċi pseudocode,
nistgħu ngħidu, ejja

13
00:00:28,040 --> 00:00:30,320
tistabbilixxi counter swap għal valur mhux żero.

14
00:00:30,320 --> 00:00:32,570
Ser naraw għaliex aħna tagħmel dan fit-tieni.

15
00:00:32,570 --> 00:00:36,090
U allura aħna irrepeti ġej
proċess sakemm il-counter tpartit huwa ta '0,

16
00:00:36,090 --> 00:00:39,910
jew sakemm nagħmlu ebda swaps fil-livelli kollha.

17
00:00:39,910 --> 00:00:43,170
>> Irrisettja l-counter tpartit biex
0 jekk ma jkunx diġà 0.

18
00:00:43,170 --> 00:00:46,420
Imbagħad tħares lejn kull
par biswit ta 'elementi.

19
00:00:46,420 --> 00:00:49,550
Jekk dawn iż-żewġ elementi huma
mhux biex, tpartit minnhom,

20
00:00:49,550 --> 00:00:51,620
żid minn 1 sa l-counter tpartit.

21
00:00:51,620 --> 00:00:53,870
Jekk int taħseb dwar
dan qabel ma Ħares,

22
00:00:53,870 --> 00:00:57,471
avviż li din se timxi aktar baxx
elementi vvalutati lejn ix-xellug

23
00:00:57,471 --> 00:01:00,720
u elementi għad-dritt ogħla vvalutati,
effettivament tagħmel dak li rridu nagħmlu,

24
00:01:00,720 --> 00:01:03,940
li hija timxi dawk il-gruppi
ta 'elementi fil-mod.

25
00:01:03,940 --> 00:01:07,035
Ejja Ħares kif dan
tista 'tidher bl-użu firxa tagħna

26
00:01:07,035 --> 00:01:10,504
li aħna użati biex jittestjaw
dawn algoritmi.

27
00:01:10,504 --> 00:01:13,420
Għandna firxa mhux magħżul hawn ukoll,
indikat mill-elementi kollha

28
00:01:13,420 --> 00:01:14,840
jkunu bl-aħmar.

29
00:01:14,840 --> 00:01:17,970
U I sett swap counter tiegħi
għal valur nonzero.

30
00:01:17,970 --> 00:01:20,610
I għażlet arbitrarjament
negattiv 1-- mhuwiex 0.

31
00:01:20,610 --> 00:01:23,840
Nixtiequ ntennu dan il-proċess
sakemm il-counter tpartit huwa ta '0.

32
00:01:23,840 --> 00:01:26,540
Dan huwa għaliex I sett tpartit tiegħi
kontra xi valur mhux żero,

33
00:01:26,540 --> 00:01:29,400
għax inkella l-
counter tpartit tkun 0.

34
00:01:29,400 --> 00:01:31,610
Aħna lanqas biss tibda l-
proċess ta 'l-algoritmu.

35
00:01:31,610 --> 00:01:33,610
Għalhekk għal darb'oħra, il-passi are--
reset-counter tpartit

36
00:01:33,610 --> 00:01:37,900
għal 0, imbagħad tħares lejn kull biswit
par, u jekk dawn qed out of order,

37
00:01:37,900 --> 00:01:40,514
tpartit lilhom, u żid 1
lejn il-counter tpartit.

38
00:01:40,514 --> 00:01:41,680
Mela ejja tibda dan il-proċess.

39
00:01:41,680 --> 00:01:44,430
Allura l-ewwel ħaġa li nagħmlu huwa
aħna waqqafna l-counter tpartit għal 0,

40
00:01:44,430 --> 00:01:46,660
u mbagħad nibdew infittxu
f'kull par biswit.

41
00:01:46,660 --> 00:01:49,140
>> Allura aħna ewwel tibda tħares lejn 5 u 2.

42
00:01:49,140 --> 00:01:52,410
Naraw li jkunu barra mill-
ordni u hekk aħna tpartit lilhom.

43
00:01:52,410 --> 00:01:53,830
U aħna żid 1 lill-counter tpartit.

44
00:01:53,830 --> 00:01:57,860
Allura issa counter swap tagħna huwa 1,
u 2 u 5 ma jkunux mixgħula.

45
00:01:57,860 --> 00:01:59,370
Issa aħna irrepeti l-proċess mill-ġdid.

46
00:01:59,370 --> 00:02:03,540
>> Aħna nħarsu lejn l-par biswit jmiss,
5 u 1-- dawn qed wkoll out of order,

47
00:02:03,540 --> 00:02:06,960
hekk aħna tpartit lilhom u żid
1 għall-kontro tpartit.

48
00:02:06,960 --> 00:02:08,900
Imbagħad aħna nħarsu lejn 5 u 3.

49
00:02:08,900 --> 00:02:13,830
Huma out of order, hekk aħna tpartit
minnhom u aħna żid 1 lejn il-counter tpartit.

50
00:02:13,830 --> 00:02:15,550
Imbagħad aħna nħarsu lejn 5 u 6.

51
00:02:15,550 --> 00:02:18,630
Huma qed sabiex, hekk aħna ma attwalment
jeħtieġ li tpartit xejn f'dan il-ħin.

52
00:02:18,630 --> 00:02:20,250
Imbagħad aħna nħarsu lejn 6 u 4.

53
00:02:20,250 --> 00:02:24,920
Huma wkoll qed out of order, hekk aħna tpartit
minnhom u aħna żid 1 lejn il-counter tpartit.

54
00:02:24,920 --> 00:02:26,230
>> Issa avviż dak li ġara.

55
00:02:26,230 --> 00:02:29,514
Imxejna mċaqalqa 6-triq kollha sa l-aħħar.

56
00:02:29,514 --> 00:02:32,180
Għalhekk fl sort għażla, jekk inti stajt
jidher li video, dak li għamilna kien

57
00:02:32,180 --> 00:02:35,290
aħna spiċċajna jiċċaqalqu l-
Elementi iżgħar fil-bini

58
00:02:35,290 --> 00:02:39,640
l-array Issortjati essenzjalment minn
xellug għal-lemin, iżgħar għall-akbar.

59
00:02:39,640 --> 00:02:43,200
Fil-każ ta 'tip bużżieqa, jekk aħna qed
wara dan algoritmu partikolari,

60
00:02:43,200 --> 00:02:46,720
aħna qed attwalment għaddejjin li tkun bini
l-array magħżula mill lemin

61
00:02:46,720 --> 00:02:49,100
għax-xellug, l-akbar għall-iżgħar.

62
00:02:49,100 --> 00:02:53,840
Aħna effettivament effervexxentement 6, il-
akbar valur, it-triq kollha sa l-aħħar.

63
00:02:53,840 --> 00:02:56,165
>> U hekk aħna issa jistgħu jiddikjaraw
li din hija magħżula,

64
00:02:56,165 --> 00:02:59,130
u fil-futur iterations--
għaddejjin mill-firxa again--

65
00:02:59,130 --> 00:03:01,280
aħna ma jkollhomx biex 6 aktar.

66
00:03:01,280 --> 00:03:03,850
Aħna biss għandek tikkunsidra
l-elementi mhux magħżul

67
00:03:03,850 --> 00:03:06,299
meta aħna qed tħares lejn pari li jmissu magħhom.

68
00:03:06,299 --> 00:03:08,340
Allura aħna lesti waħda
jgħaddu sort bużżieqa.

69
00:03:08,340 --> 00:03:11,941
Allura issa immorru lura għall-mistoqsija,
irrepeti sakemm il-counter tpartit huwa ta '0.

70
00:03:11,941 --> 00:03:13,690
Ukoll l-counter tpartit
huwa ta '4, hekk aħna qed tmur

71
00:03:13,690 --> 00:03:15,410
biex iżommu tirrepeti dan il-proċess mill-ġdid.

72
00:03:15,410 --> 00:03:19,180
>> Aħna ser reset-counter tpartit
għal 0, u ħarsa lejn kull par biswit.

73
00:03:19,180 --> 00:03:21,890
Allura nibdew il 2 u 1-- dawn qed
out of order, hekk aħna tpartit lilhom

74
00:03:21,890 --> 00:03:23,620
u aħna żid 1 lejn il-counter tpartit.

75
00:03:23,620 --> 00:03:25,490
2 u 3, li qed fl-ordni.

76
00:03:25,490 --> 00:03:27,060
Aħna ma bżonn li tagħmel xejn.

77
00:03:27,060 --> 00:03:28,420
3 u 5 huma fl-ordni.

78
00:03:28,420 --> 00:03:30,150
Aħna ma bżonn li tagħmel xejn hemmhekk.

79
00:03:30,150 --> 00:03:32,515
>> 5 u 4, jkunu barra
ta 'ordni, u hekk aħna

80
00:03:32,515 --> 00:03:35,130
jeħtieġ li tpartit lilhom u żid
1 għall-kontro tpartit.

81
00:03:35,130 --> 00:03:38,880
U issa konna mċaqalqa 5,
l-akbar element li jmiss,

82
00:03:38,880 --> 00:03:40,920
sa l-aħħar tal-porzjon mhux magħżul.

83
00:03:40,920 --> 00:03:44,360
Allura aħna issa jistgħu jċemplu li
parti tal-porzjon magħżula.

84
00:03:44,360 --> 00:03:47,180
>> Issa inti qed tħares lejn il-
screen u probabbilment tista 'tgħid,

85
00:03:47,180 --> 00:03:50,130
kif jista I, li l-firxa
huwa magħżul dritt issa.

86
00:03:50,130 --> 00:03:51,820
Iżda aħna ma jistax jipprova li għadu.

87
00:03:51,820 --> 00:03:54,359
Aħna ma jkollhom garanzija
li huwa magħżula.

88
00:03:54,359 --> 00:03:56,900
Iżda din hija fejn l-iswap
counter għaddej biex tidħol fin-nofs.

89
00:03:56,900 --> 00:03:59,060
>> Allura aħna ve kompletati pass.

90
00:03:59,060 --> 00:04:00,357
Il-counter tpartit huwa 2.

91
00:04:00,357 --> 00:04:02,190
Allura aħna qed tmur biex jirrepeti
dan il-proċess mill-ġdid,

92
00:04:02,190 --> 00:04:04,290
irrepeti sakemm il-counter tpartit huwa ta '0.

93
00:04:04,290 --> 00:04:05,550
Irrisettja l-counter tpartit għal 0.

94
00:04:05,550 --> 00:04:06,820
Allura aħna ser reset.

95
00:04:06,820 --> 00:04:09,810
>> Issa tħares lejn kull par biswit.

96
00:04:09,810 --> 00:04:11,880
Li fl-ordni, 1 u 2.

97
00:04:11,880 --> 00:04:13,590
2 u 3 huma fl-ordni.

98
00:04:13,590 --> 00:04:15,010
3 u 4 huma fl-ordni.

99
00:04:15,010 --> 00:04:19,250
Allura f'dan il-punt, l-avviż konna kompletati
tħares lejn kull par biswit,

100
00:04:19,250 --> 00:04:22,530
iżda l-counter tpartit għadu 0.

101
00:04:22,530 --> 00:04:25,520
>> Jekk aħna ma jkollhom jaqilbu
kull element, allura dawn

102
00:04:25,520 --> 00:04:28,340
Jeħtiġilhom ikunu, minn
saħħa ta 'dan il-proċess.

103
00:04:28,340 --> 00:04:32,000
U għalhekk effiċjenza ta 'tipi,
li xjenzjati we kompjuter imħabba,

104
00:04:32,000 --> 00:04:35,560
huwa issa tista 'tiddikjara
l-array kollu għandu

105
00:04:35,560 --> 00:04:38,160
jiġu magħżula, għaliex aħna ma
għandek tpartit xi elementi.

106
00:04:38,160 --> 00:04:40,380
Li pretty sbieħ.

107
00:04:40,380 --> 00:04:43,260
>> Allura x'inhu l-agħar każ
xenarju bi sort bużżieqa?

108
00:04:43,260 --> 00:04:46,240
Fl-agħar każ li l-firxa hija
sabiex kompletament reverse,

109
00:04:46,240 --> 00:04:49,870
u hekk aħna li bużżieqa kull
mill-elementi kbar kollha

110
00:04:49,870 --> 00:04:51,780
il-mod madwar l-firxa.

111
00:04:51,780 --> 00:04:55,350
U aħna effettivament għandhom ukoll
bużżieqa l-elementi kollha żgħar lura

112
00:04:55,350 --> 00:04:57,050
it-triq kollha madwar l-firxa, wisq.

113
00:04:57,050 --> 00:05:01,950
Allura kull wieħed mill-elementi n trid timxi
firxa kollha tas-elementi l-oħra n.

114
00:05:01,950 --> 00:05:04,102
Allura dak l-agħar każ.

115
00:05:04,102 --> 00:05:05,810
Fl-aħjar każ
xenarju għalkemm, dan huwa

116
00:05:05,810 --> 00:05:07,880
kemmxejn differenti minn tip selezzjoni.

117
00:05:07,880 --> 00:05:10,040
Il-firxa hija diġà
magħżula meta immorru fil.

118
00:05:10,040 --> 00:05:12,550
Aħna ma jkollhom jagħmlu xi
swaps fuq l-ewwel pass.

119
00:05:12,550 --> 00:05:14,940
Allura nistgħu nħarsu
fil inqas l-elementi, id-dritt?

120
00:05:14,940 --> 00:05:18,580
Aħna ma jkollhom jirrepetu dan
jipproċessaw numru ta 'drabi matul.

121
00:05:18,580 --> 00:05:19,540
>> Allura dak li jfisser?

122
00:05:19,540 --> 00:05:22,390
Allura x'inhu l-agħar każ
għall sort bużżieqa, u x'hemm

123
00:05:22,390 --> 00:05:25,330
l aħjar każ għall tip bużżieqa?

124
00:05:25,330 --> 00:05:27,770
Ridt raden dan?

125
00:05:27,770 --> 00:05:32,420
Fl-agħar każ inti għandek jtenni
madwar l-elementi kollha n n darbiet.

126
00:05:32,420 --> 00:05:34,220
Allura l-agħar każ hija n kwadrat.

127
00:05:34,220 --> 00:05:36,550
>> Jekk il-firxa hija perfettament
Issortjati għalkemm, inti biss

128
00:05:36,550 --> 00:05:38,580
għandek tfittex lejn kull
mill-elementi darba.

129
00:05:38,580 --> 00:05:42,670
U jekk il-counter tpartit għadu 0,
inti tista 'tgħid dan array huwa magħżul.

130
00:05:42,670 --> 00:05:45,780
U għalhekk fl-aħjar każ, dan huwa
attwalment aħjar minn għażla

131
00:05:45,780 --> 00:05:49,230
sort-- huwa omega ta n.

132
00:05:49,230 --> 00:05:50,270
>> Jien Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Dan huwa CS50.

134
00:05:52,140 --> 00:05:54,382