1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Sort Inserzjoni]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Università ta 'Harvard]

3
00:00:04,240 --> 00:00:07,290
[Dan huwa CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Ejja tagħti ħarsa lejn it-tip inserzjoni, algoriżmu għat-teħid ta 'lista ta' numri u l-għażla tagħhom.

5
00:00:13,060 --> 00:00:18,300
Algoritmu, ftakar, huwa sempliċement proċedura ta 'pass pass għall-kisba ta' kompitu.

6
00:00:18,300 --> 00:00:23,640
L-idea bażika wara sort inserzjoni, huwa li jaqsam lista tagħna f'żewġ porzjonijiet,

7
00:00:23,640 --> 00:00:26,580
porzjon magħżula u porzjon mhux magħżul.

8
00:00:26,580 --> 00:00:29,290
>> F'kull pass ta 'l-algoritmu, numru jiġi mċaqlaq

9
00:00:29,290 --> 00:00:32,439
mill-porzjon mhux magħżul għall-porzjon magħżul

10
00:00:32,439 --> 00:00:35,680
sakemm eventwalment l-lista sħiħa huwa magħżul.

11
00:00:35,680 --> 00:00:43,340
Hawn hi l-lista ta 'sitt numri mhux magħżul - 23, 42, 4, 16, 8, u 15.

12
00:00:43,340 --> 00:00:47,680
Peress li dawn in-numri mhumiex kollha f'ordni axxendenti, dawn qed jintbagħtu f'volumi kbar.

13
00:00:47,680 --> 00:00:53,890
Minħabba li aħna ma bdew issortjar għadhom, aħna ser jikkunsidraw l-elementi kollha 6 porzjon mhux magħżul tagħna.

14
00:00:53,890 --> 00:00:59,270
>> Ladarba nibdew issortjar, aħna ser tpoġġi dawn in-numri magħżula fuq ix-xellug ta 'dawn.

15
00:00:59,270 --> 00:01:03,600
Allura, ejja tibda bil 23, l-ewwel element fil-lista tagħna.

16
00:01:03,600 --> 00:01:06,930
Aħna ma jkollu l-ebda elementi fil-porzjon magħżul tagħna għadhom,

17
00:01:06,930 --> 00:01:12,460
hekk ejja sempliċement jikkunsidraw 23 tkun il-bidu u t-tmiem tal-porzjon magħżul tagħna.

18
00:01:12,460 --> 00:01:16,510
Issa, porzjon magħżula tagħna numru wieħed, 23,

19
00:01:16,510 --> 00:01:20,260
u l-porzjon mhux magħżul tagħna dawn in-numri 5.

20
00:01:20,260 --> 00:01:27,320
Ejja issa daħħal in-numru li jmiss fil-porzjon mhux magħżul tagħna, 42, fis-porzjon magħżula.

21
00:01:27,320 --> 00:01:35,930
>> Biex tagħmel dan, aħna ser bżonn li jqabblu l-42 sa l-23 - l-uniku element fil-porzjon magħżul tagħna s'issa.

22
00:01:35,930 --> 00:01:41,980
Tnejn u erbgħin hija akbar minn 23, sabiex inkunu nistgħu sempliċiment jehmeż 42 sa l-aħħar

23
00:01:41,980 --> 00:01:45,420
tal-porzjon magħżul tal-lista. Great!

24
00:01:45,420 --> 00:01:51,850
Issa porzjon magħżula tagħna għandha żewġ elementi, u porzjon mhux magħżul tagħna għandha erba 'elementi.

25
00:01:51,850 --> 00:01:57,200
Allura, ejja issa jimxu lejn il-4, l-element li jmiss fil-porzjon mhux magħżul.

26
00:01:57,200 --> 00:02:00,230
Għalhekk, fejn għandhom dan jitpoġġa fil-porzjon magħżula?

27
00:02:00,230 --> 00:02:04,220
>> Ftakar, irridu li tqiegħed dan in-numru sabiex magħżula

28
00:02:04,220 --> 00:02:08,680
hekk porzjon magħżula tagħna jibqa korrett magħżula fil-ħinijiet kollha.

29
00:02:08,680 --> 00:02:14,380
Jekk aħna post-4 għad-dritt ta 'l-42, allura lista tagħna se jkun out of order.

30
00:02:14,380 --> 00:02:18,380
Allura, ejja tkompli miexja lemin għax-xellug fil-porzjon sort tagħna.

31
00:02:18,380 --> 00:02:23,260
Hekk kif nersqu, ejja shift kull numru isfel post biex tagħmel spazju għall-numru ġdid.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 huwa wkoll anqas minn 23, hekk aħna ma tista 'poġġih lanqas hawn.

33
00:02:31,740 --> 00:02:34,480
Ejja jċaqalqu l-23 dritt f'post wieħed.

34
00:02:36,500 --> 00:02:43,120
>> Dan ifisser aħna tixtieq li post l-4 fl-islott ewwel fil-porzjon magħżula.

35
00:02:43,120 --> 00:02:46,300
Avviż kif dan l-ispazju fil-lista kienet diġà vojta,

36
00:02:46,300 --> 00:02:51,120
għaliex aħna kont qed jiċċaqilqu elementi magħżula isfel kif konna jiltaqgħu magħhom minnhom.

37
00:02:51,120 --> 00:02:52,740
Kull dritt. Allura, aħna qed nofs hemm.

38
00:02:52,740 --> 00:02:57,990
Ejja tkompli algoritmu tagħna billi ddaħħal il-16 fil-porzjon magħżula.

39
00:02:59,260 --> 00:03:03,820
Sittax huwa inqas minn 42, hekk ejja ċċaqlaq il-42 lejn il-lemin.

40
00:03:05,700 --> 00:03:10,190
Sittax huwa wkoll anqas minn 23, hekk ejja wkoll bidla dak l-element.

41
00:03:11,790 --> 00:03:20,820
>> Issa, 16 hija akbar minn 4. Għalhekk, jidher qisu aħna tixtieq li daħħal il-16 bejn l-4 u l-23.

42
00:03:20,820 --> 00:03:24,620
Filwaqt li jiċċaqilqu permezz tal-porzjon magħżula tal-lista mill-lemin għax-xellug,

43
00:03:24,620 --> 00:03:29,160
4 hija l-ewwel numru Rajna li huwa iżgħar min-numru

44
00:03:29,160 --> 00:03:31,540
aħna qed tipprova li daħħal.

45
00:03:31,540 --> 00:03:35,820
Allura, issa nistgħu daħħal il-16 fil dan slot vojta,

46
00:03:35,820 --> 00:03:40,520
li, ftakar, aħna ve maħluqa mill-elementi li jiċċaqalqu fil-porzjon xorta fuq

47
00:03:40,520 --> 00:03:43,340
kif konna jiltaqgħu magħhom minnhom.

48
00:03:43,340 --> 00:03:47,900
>> Kull dritt. Issa, għandna erba 'elementi magħżula u żewġ elementi mhux magħżul.

49
00:03:47,900 --> 00:03:51,600
Allura, ejja jimxu l-8 fil-porzjon magħżula.

50
00:03:51,600 --> 00:03:55,010
Tmien huwa inqas minn 42.

51
00:03:55,010 --> 00:03:56,940
Tmien huwa inqas minn 23.

52
00:03:56,940 --> 00:04:00,230
U 8 hija inqas minn 16.

53
00:04:00,230 --> 00:04:03,110
Imma 8 hija akbar minn 4.

54
00:04:03,110 --> 00:04:07,280
Allura, aħna tixtieq li daħħal l-8 bejn l-4 u l-16.

55
00:04:09,070 --> 00:04:13,650
U issa aħna biss għandhom element wieħed aktar xellug biex issolvi - l-15.

56
00:04:13,950 --> 00:04:16,589
Ħmistax huwa inqas minn 42,

57
00:04:16,589 --> 00:04:19,130
Ħmistax huwa inqas minn 23.

58
00:04:19,130 --> 00:04:21,750
U 15 hija anqas minn 16.

59
00:04:21,750 --> 00:04:24,810
Iżda 15 hija akbar minn 8.

60
00:04:24,810 --> 00:04:27,440
>> Allura, hawn huwa fejn irridu li jagħmlu inserzjoni finali tagħna.

61
00:04:28,770 --> 00:04:30,330
U aħna qed isir.

62
00:04:30,330 --> 00:04:33,540
Għandna l-ebda elementi aktar fil-porzjon mhux magħżul,

63
00:04:33,540 --> 00:04:36,670
u l-porzjon magħżula tagħna huwa fl-ordni korretta.

64
00:04:36,670 --> 00:04:40,270
In-numri huma ordnati mill-iżgħar sa l-akbar.

65
00:04:40,270 --> 00:04:44,330
Allura, ejja tagħti ħarsa lejn uħud pseudocode li jiddeskrivi l-passi aħna biss mwettqa.

66
00:04:46,760 --> 00:04:51,740
>> Fl-linja 1, nistgħu naraw li għandna bzonn biex jtenni fuq kull element fil-lista

67
00:04:51,740 --> 00:04:57,060
ħlief l-ewwel, peress li l-ewwel element fil-porzjon mhux magħżul sempliċiment se jsiru

68
00:04:57,060 --> 00:05:00,220
l-ewwel element fil-porzjon magħżula.

69
00:05:00,220 --> 00:05:06,320
Fuq linji 2 u 3, aħna qed iżżomm rekord tal-post attwali tagħna fil-porzjon mhux magħżul.

70
00:05:06,320 --> 00:05:10,450
Element tirrapreżenta in-numru aħna bħalissa qed jiċċaqilqu fis-porzjon magħżula,

71
00:05:10,450 --> 00:05:15,600
u j tirrappreżenta indiċi tagħna fis-porzjon mhux magħżul.

72
00:05:15,600 --> 00:05:20,980
>> Fuq linja 4, aħna qed mtennija mill-parti magħżula mill-lemin għax-xellug.

73
00:05:20,980 --> 00:05:26,010
Aħna tixtieq li twaqqaf iterazzjoni ladarba l-element għall-xellug tal-pożizzjoni attwali tagħna

74
00:05:26,010 --> 00:05:30,050
huwa inqas mill-element aħna qed jippruvaw daħħal.

75
00:05:30,050 --> 00:05:35,600
Fuq linja 5, aħna qed tiċċaqlaq kull element niltaqgħu spazju wieħed lejn il-lemin.

76
00:05:35,600 --> 00:05:40,950
B'dan il-mod, aħna ser ikollhom spazju vojt li ddaħħal fil meta insibu l-ewwel element

77
00:05:40,950 --> 00:05:44,080
inqas mill-element aħna qed jiċċaqalqu.

78
00:05:44,080 --> 00:05:50,800
Fuq linja 6, aħna qed aġġornament counter tagħna biex tkompli timxi xellug ġol-parti magħżula.

79
00:05:50,800 --> 00:05:56,860
Fl-aħħarnett, fuq il-linja 7, aħna qed tiddaħħal l-element fil-porzjon magħżula tal-lista.

80
00:05:56,860 --> 00:06:00,020
>> Aħna nafu li huwa okay li ddaħħal fil-pożizzjoni j,

81
00:06:00,020 --> 00:06:05,360
għaliex konna diġà mxew l-element li jintuża biex tkun hemm spazju wieħed lejn il-lemin.

82
00:06:05,360 --> 00:06:09,460
Ftakar, aħna qed jiċċaqalqu permezz tal-porzjon magħżula mill-lemin għax-xellug,

83
00:06:09,460 --> 00:06:13,960
imma aħna qed jiċċaqilqu permezz tal-porzjon mhux magħżul mix-xellug għal-lemin.

84
00:06:13,960 --> 00:06:19,090
Kull dritt. Ejja issa tagħti ħarsa lejn kemm running ħa algoritmu li.

85
00:06:19,090 --> 00:06:25,300
Aħna ser ewwel titlob il-kwistjoni kemm żmien ma jieħdu għal dan algoritmu jiddekorri fl-agħar każ.

86
00:06:25,300 --> 00:06:29,040
Ifakkar li aħna jirrappreżentaw din id-darba t-tħaddim ma O notazzjoni Big.

87
00:06:32,530 --> 00:06:38,500
Sabiex issolvi lista tagħna, kellna biex jtenni fuq l-elementi fil-porzjon mhux magħżul,

88
00:06:38,500 --> 00:06:43,430
u għal kull wieħed minn dawk l-elementi, potenzjalment fuq l-elementi kollha fil-porzjon magħżula.

89
00:06:43,430 --> 00:06:47,950
Intuwittivament, dan ħsejjes bħal O (n ^ 2) operazzjoni.

90
00:06:47,950 --> 00:06:51,840
>> Ħarsa lejn pseudocode tagħna, aħna għandna loop nested ġewwa ieħor loop,

91
00:06:51,840 --> 00:06:55,290
li, fil-fatt, ħsejjes bħal O (n ^ 2) operazzjoni.

92
00:06:55,290 --> 00:07:01,590
Madankollu, il-porzjon magħżula ta 'lista ma tinkludi l-lista sħiħa sa l-aħħar ħafna.

93
00:07:01,590 --> 00:07:06,920
Still, nistgħu potenzjalment daħħal element ġdid fil-bidu nett tal-porzjon magħżul

94
00:07:06,920 --> 00:07:09,320
fuq kull iterazzjoni ta 'l-algoritmu,

95
00:07:09,320 --> 00:07:14,500
li jfisser li aħna'd nħarsu lejn kull element bħalissa fil-porzjon magħżula.

96
00:07:14,500 --> 00:07:20,090
Allura, li jfisser li għandna jistgħu potenzjalment jagħmlu waħda paragun għat-tieni element,

97
00:07:20,090 --> 00:07:24,660
2 paraguni għat-tielet element, u l-bqija.

98
00:07:24,660 --> 00:07:32,480
Allura, in-numru totali ta 'passi hija s-somma ta' l-interi mill-1 għat-tul tal-lista minus 1.

99
00:07:32,480 --> 00:07:35,240
Nistgħu jirrappreżentaw dan bil-kalkolu totali.

100
00:07:41,170 --> 00:07:47,270
>> Aħna mhux se tidħol fis ammonti totali hawnhekk, iżda jirriżulta li din l-addizzjoni hija ugwali għal

101
00:07:47,270 --> 00:07:57,900
n (n - 1) aktar minn 2, li huwa n ekwivalenti ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Meta wieħed jitkellem dwar runtime asintotiku,

103
00:08:00,800 --> 00:08:05,170
din n ^ 2 terminu huwa ser jiddominaw dan it-terminu n.

104
00:08:05,170 --> 00:08:11,430
Allura, sort inserzjoni huwa Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
X'jiġri jekk aħna dam tip inklużjoni fil-lista diġà magħżula.

106
00:08:16,150 --> 00:08:20,960
F'dak il-każ, aħna'd sempliċiment jibnu l-porzjon magħżula mix-xellug għal-lemin.

107
00:08:20,960 --> 00:08:25,050
Allura, aħna ser bżonn biss fuq l-ordni ta 'passi n.

108
00:08:25,050 --> 00:08:29,740
>> Dan ifisser li tip inserzjoni għandu prestazzjoni aħjar każ ta 'ln,

109
00:08:29,740 --> 00:08:34,130
li nirrappreżentaw mal Ω (n).

110
00:08:34,130 --> 00:08:36,190
U li hija għal tip inserzjoni,

111
00:08:36,190 --> 00:08:40,429
biss wieħed mill-algoritmi ħafna nistgħu nużaw biex issolvi lista.

112
00:08:40,429 --> 00:08:43,210
Jisimni Tommy, u dan huwa CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, inti biss ma tistax tieqaf li ladarba jibda.

115
00:09:01,620 --> 00:09:04,760
Oh, aħna ma li - Boom >>!