1
00:00:00,000 --> 00:00:02,826
>> [Daqq tal-mużika]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Allura tip inserzjoni hija ieħor
algoritmu nistgħu nużaw biex issolvi firxa.

4
00:00:09,370 --> 00:00:12,350
L-idea wara dan algoritmu
huwa biex tinbena array Issortjat tiegħek

5
00:00:12,350 --> 00:00:19,670
fis-seħħ, elementi ċaqliq minn
il-mod kif tmur, biex tagħmel spazju.

6
00:00:19,670 --> 00:00:22,240
Dan huwa kemmxejn differenti
minn tip selezzjoni jew bżieżaq

7
00:00:22,240 --> 00:00:25,460
sort, per eżempju, fejn
aħna qed jaġġusta l-postijiet,

8
00:00:25,460 --> 00:00:26,910
fejn aħna qed jagħmlu swaps.

9
00:00:26,910 --> 00:00:29,760
>> F'dan il-każ dak li aħna qed attwalment
tagħmel huwa elementi li jiżżerżqu

10
00:00:29,760 --> 00:00:31,390
fuq, barra mill-mod.

11
00:00:31,390 --> 00:00:34,030
Kif jaħdem dan algoritmu
jaħdmu pseudocode?

12
00:00:34,030 --> 00:00:37,646
Well ejja biss b'mod arbitrarju jgħidu li l-
ewwel element tal-array huwa magħżul.

13
00:00:37,646 --> 00:00:38,770
Aħna qed tinbena fil-post.

14
00:00:38,770 --> 00:00:42,660
>> Aħna gonna jmorru element wieħed fi żmien u
tinbena, u għalhekk l-ewwel ħaġa li naraw

15
00:00:42,660 --> 00:00:43,890
huwa firxa element wieħed.

16
00:00:43,890 --> 00:00:47,720
U bid-definizzjoni, wieħed
element array huwa magħżul.

17
00:00:47,720 --> 00:00:50,850
>> Imbagħad aħna ser irrepeti dan il-proċess until--
aħna ser irrepeti l-proċess li ġej

18
00:00:50,850 --> 00:00:52,900
sakemm l-elementi kollha huma magħżula.

19
00:00:52,900 --> 00:00:57,770
Ħares lejn l-element mhux magħżul li jmiss u
daħħalha fil-porzjon magħżula,

20
00:00:57,770 --> 00:01:01,209
billi ċċaqlaq-numru meħtieġ
ta 'elementi barra mill-mod.

21
00:01:01,209 --> 00:01:03,750
Nisperaw li dan viżwalizzazzjoni
se tgħinek tara eżattament x'hemm

22
00:01:03,750 --> 00:01:05,980
għaddej ma sort inserzjoni.

23
00:01:05,980 --> 00:01:08,010
>> Għalhekk għal darb'oħra, hawnhekk tagħna
firxa mhux magħżul kollu,

24
00:01:08,010 --> 00:01:10,970
l-elementi kollha indikati bl-aħmar.

25
00:01:10,970 --> 00:01:13,320
U ejja isegwu l-
passi ta 'pseudocode tagħna.

26
00:01:13,320 --> 00:01:16,970
L-ewwel ħaġa li għandna nagħmlu, huwa nsejħu l
ewwel element tal-firxa, magħżula.

27
00:01:16,970 --> 00:01:20,920
Allura aħna qed biss jgħidu gonna
ħames, int issa magħżula.

28
00:01:20,920 --> 00:01:24,570
>> Imbagħad aħna nħarsu lejn il-li jmiss
element mhux magħżul mill-firxa

29
00:01:24,570 --> 00:01:27,610
u rridu biex jiddaħħal li
fil-porzjon magħżula,

30
00:01:27,610 --> 00:01:29,750
billi ċċaqlaq elementi fuq.

31
00:01:29,750 --> 00:01:33,470
Allura tnejn huwa mhux magħżul li jmiss
element tad-array.

32
00:01:33,470 --> 00:01:36,250
Ovvjament jappartjeni qabel l-
ħames, hekk dak li aħna qed gonna do

33
00:01:36,250 --> 00:01:41,580
huwa tip ta 'istiva żewġ imwarrba għat-tieni,
bidla ħamsa fuq, u mbagħad daħħal żewġ

34
00:01:41,580 --> 00:01:43,210
qabel ħames, fejn għandhom imorru.

35
00:01:43,210 --> 00:01:45,280
U issa nistgħu ngħidu li żewġ huwa magħżul.

36
00:01:45,280 --> 00:01:48,400
>> Allura kif tista 'tara, konna biss s'issa
ħares lejn żewġ elementi tal-firxa.

37
00:01:48,400 --> 00:01:50,600
Aħna ma ħares lejn il-
mistrieħ fil-livelli kollha, iżda konna

38
00:01:50,600 --> 00:01:54,582
ltqajna dawn iż-żewġ elementi magħżula mill
mod tal-mekkaniżmu ċaqliq.

39
00:01:54,582 --> 00:01:56,410
>> Allura aħna irrepeti l-proċess mill-ġdid.

40
00:01:56,410 --> 00:01:58,850
Ħares lejn il-mhux magħżul li jmiss
element, li wieħed.

41
00:01:58,850 --> 00:02:04,010
Ejja tiddeċiedi li twarrab għat-tieni,
bidla kollox fuq, u mqiegħda wieħed

42
00:02:04,010 --> 00:02:05,570
fejn għandhom imorru.

43
00:02:05,570 --> 00:02:08,110
>> Għal darb'oħra, xorta, konna biss qatt
ħares lejn wieħed, tnejn, u ħamsa.

44
00:02:08,110 --> 00:02:12,480
Ma nafux x'iktar huwa li ġejjin,
imma konna magħżula dawk it-tliet elementi.

45
00:02:12,480 --> 00:02:16,030
>> Element mhux magħżul li jmiss huwa
tlieta, hekk aħna ser dan għandu jiġi annullat.

46
00:02:16,030 --> 00:02:18,200
Aħna ser bidla fuq dak li aħna
jeħtieġ li, din id-darba

47
00:02:18,200 --> 00:02:21,820
mhux kollox bħal fil-preċedenti
żewġ każijiet, huwa biss l-ħames.

48
00:02:21,820 --> 00:02:25,440
U allura aħna ser twaħħal tlieta fil-
bejn it-tnejn u l-ħames.

49
00:02:25,440 --> 00:02:27,849
>> Sitt huwa li jmiss mhux magħżul
element lill-firxa.

50
00:02:27,849 --> 00:02:31,140
U fil-fatt sitt jkun iktar minn ħamsa, sabiex
aħna lanqas biss bżonn tagħmel xi iskambji.

51
00:02:31,140 --> 00:02:35,710
Nistgħu biss tindi sitta dritt fuq
l-aħħar tal-porzjon magħżula.

52
00:02:35,710 --> 00:02:38,270
>> Fl-aħħar nett, erba huwa l-
aħħar element mhux magħżul.

53
00:02:38,270 --> 00:02:42,060
Allura aħna ser dan għandu jiġi annullat, bidla fuq
l-elementi għandna bżonn li ċċaqlaq fuq,

54
00:02:42,060 --> 00:02:43,780
u mbagħad titqiegħed erba fejn jappartjeni.

55
00:02:43,780 --> 00:02:46,400
U issa nħarsu, konna sort
ta 'l-elementi.

56
00:02:46,400 --> 00:02:48,150
Avviż bil inserzjoni
sort, aħna ma kellhiex

57
00:02:48,150 --> 00:02:50,240
li jmorru quddiem u lura madwar l-firxa.

58
00:02:50,240 --> 00:02:54,720
Aħna biss marru madwar il-firxa
żmien wieħed, u aħna qalbu affarijiet

59
00:02:54,720 --> 00:02:59,870
li aħna'd diġà ltaqgħu magħhom, sabiex
biex tagħmel spazju għall-elementi ġodda.

60
00:02:59,870 --> 00:03:02,820
>> Allura x'inhu l-agħar każ
xenarju bi sort inserzjoni?

61
00:03:02,820 --> 00:03:05,090
Fl-agħar każ, il-
firxa hija fl-ordni reverse.

62
00:03:05,090 --> 00:03:11,180
Inti għandek li ċċaqlaq kull wieħed mill-elementi N
sa pożizzjonijiet n, kull darba we wieħed

63
00:03:11,180 --> 00:03:12,880
jagħmlu inserzjoni.

64
00:03:12,880 --> 00:03:15,720
Li l-lott ta 'ċaqliq.

65
00:03:15,720 --> 00:03:18,014
>> Fl-aħjar każ, il-
array huwa perfettament riżolta.

66
00:03:18,014 --> 00:03:20,680
U tip simili dak li ġara
ma 'ħames u sitt fl-eżempju,

67
00:03:20,680 --> 00:03:23,779
fejn nistgħu biss tindi fuq
mingħajr ma jkollhom jagħmlu xi ċaqliq,

68
00:03:23,779 --> 00:03:24,820
aħna'd essenzjalment tagħmel dan.

69
00:03:24,820 --> 00:03:27,560
>> Jekk inti jimmaġina li tagħna
firxa kienet waħda permezz sitta,

70
00:03:27,560 --> 00:03:29,900
aħna'd tibda off billi
tiddikjara wieħed huwa magħżul.

71
00:03:29,900 --> 00:03:33,300
Żewġ wasal wara waħda sabiex inkunu nistgħu biss
jgħidu, OK, ukoll wieħed u tnejn huma magħżula.

72
00:03:33,300 --> 00:03:36,190
Tliet wasal wara żewġ hekk, OK,
wieħed u tnejn u tlieta huma magħżula.

73
00:03:36,190 --> 00:03:39,590
>> Aħna ma tagħmel xi swaps, aħna qed
biss jiċċaqalqu din il-linja arbitrarja

74
00:03:39,590 --> 00:03:42,460
bejn magħżula u mhux magħżula kif immorru.

75
00:03:42,460 --> 00:03:46,646
B'mod effettiv kemm għamilna fl-eżempju,
tidwir elementi blu, kif aħna tipproċedi.

76
00:03:46,646 --> 00:03:48,270
Allura x'inhu l-runtime agħar każ, allura?

77
00:03:48,270 --> 00:03:51,854
Ftakar, jekk irridu bidla kull wieħed
l-elementi n pożizzjonijiet n possibilment,

78
00:03:51,854 --> 00:03:54,020
nisperaw li jagħtik
idea li l-agħar każ

79
00:03:54,020 --> 00:03:57,770
runtime huwa O Big ta n kwadrat.

80
00:03:57,770 --> 00:04:00,220
>> Jekk il-firxa hija perfettament
magħżula, kollha għandna nagħmlu

81
00:04:00,220 --> 00:04:04,480
huwa tħares lejn kull element wieħed
darba, u allura aħna qed isir.

82
00:04:04,480 --> 00:04:08,440
Allura fil-każ aħjar, huwa omega ta n.

83
00:04:08,440 --> 00:04:09,490
>> Jien Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Dan huwa CS50.

85
00:04:11,760 --> 00:04:13,119