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

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[Hoc est CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Lets 'take a inviso insertionem modi, an algorithm pro captus a album numerorum et voluptua eos.

5
00:00:13,060 --> 00:00:18,300
Algorithm est memoria, ratio perficiendi GRADATUS simpliciter opus.

6
00:00:18,300 --> 00:00:23,640
Basic idea post insertionem modi, est dividere nostrum album in duas portiones,

7
00:00:23,640 --> 00:00:26,580
a sorted partem et an Unsorted portio est.

8
00:00:26,580 --> 00:00:29,290
>> Quolibet gradu algorithm numerus motus

9
00:00:29,290 --> 00:00:32,439
a Unsorted partem sorted portio

10
00:00:32,439 --> 00:00:35,680
donec eventually totius album est sorted.

11
00:00:35,680 --> 00:00:43,340
Hic numerus numero sex Unsorted - XXIII, XLII, IV, XVI, VIII et XV.

12
00:00:43,340 --> 00:00:47,680
Quia hi numeri non sunt omnes in ascendendo ordo, erant 'Unsorted.

13
00:00:47,680 --> 00:00:53,890
Quoniam sumus non inchoatur voluptua tamen, puteus 'considerare de omnibus sex elementa nostri Unsorted portio est.

14
00:00:53,890 --> 00:00:59,270
>> Quondam nos satus voluptua, puteus 'mitte illas sorted numeris ad sinistram ex istis.

15
00:00:59,270 --> 00:01:03,600
Itaque XXIII principium est primum in elementum lacus.

16
00:01:03,600 --> 00:01:06,930
Non habemus cuiusquam elementi in nostra sorted portio tamen,

17
00:01:06,930 --> 00:01:12,460
sic lets simpliciter considerare XXIII esse initium et finis nostrae sorted portio est.

18
00:01:12,460 --> 00:01:16,510
Sed ille nostrae pars commoda numero XXIII,

19
00:01:16,510 --> 00:01:20,260
et nostra Unsorted pars his quinque numerorum.

20
00:01:20,260 --> 00:01:27,320
Lets nunc inserere postero numerus in nostra Unsorted portionem, XLII, in sorted portio est.

21
00:01:27,320 --> 00:01:35,930
>> Id est, ad opust XXIII conferre XLII - digestus in partem unam tantum materiam.

22
00:01:35,930 --> 00:01:41,980
XXIII amplius quadraginta duae, additis XLII possumus ad hoc duntaxat

23
00:01:41,980 --> 00:01:45,420
de sorted portio list. Magna!

24
00:01:45,420 --> 00:01:51,850
Autem noster sorted pars duo elementa, et nostra Unsorted pars quatuor elementa.

25
00:01:51,850 --> 00:01:57,200
Itaque Nunc IV feratur ad proxima pars Unsorted elementum.

26
00:01:57,200 --> 00:02:00,230
Proinde ubi, debet hoc poni in sorted portio?

27
00:02:00,230 --> 00:02:04,220
>> Recordare, nos volo ut pone istud numerum in sorted ordinem

28
00:02:04,220 --> 00:02:08,680
ita noster sorted relictaque portione recte sorted in omni tempore.

29
00:02:08,680 --> 00:02:14,380
XLII Si autem rectum IV ponimus, ex quo tunc erunt nomina.

30
00:02:14,380 --> 00:02:18,380
Sic, lets perseverant movendo ius-ut-remansisset in sort portio est.

31
00:02:18,380 --> 00:02:23,260
Sicut et nos movere, lets amoveo quisque numerus descendit locum ad locum faciunt novus enim numerus.

32
00:02:25,440 --> 00:02:31,740
Bene, quam etiam IV XXIII, ita neque hic locus non est.

33
00:02:31,740 --> 00:02:34,480
Lets movere XXIII ius unum locum.

34
00:02:36,500 --> 00:02:43,120
>> Ut opes wed 'amo ut ponunt IV in primum socors in sorted portio est.

35
00:02:43,120 --> 00:02:46,300
Ecce ut iam vacuo spatio album,

36
00:02:46,300 --> 00:02:51,120
quia nos Ive 'been movendo sorted elementa down ut weve occurrit.

37
00:02:51,120 --> 00:02:52,740
Omni jure. Sic, sumus ultro insequuntur ibi.

38
00:02:52,740 --> 00:02:57,990
Lets pergere algorithm inserendo XVI in sorted portio est.

39
00:02:59,260 --> 00:03:03,820
XLII sex minus, ita nec ad ius transferre XLII.

40
00:03:05,700 --> 00:03:10,190
Sedecim etiam minor est XXIII, sic fiat scriptor etiam amoveo qui elementum.

41
00:03:11,790 --> 00:03:20,820
>> Sed maior IV XVI. Ergo videtur quod libet interponere inter IV et XVI XXIII.

42
00:03:20,820 --> 00:03:24,620
Dum movens per sorted portio list a dextro ad sinistrum,

43
00:03:24,620 --> 00:03:29,160
IV vidi numerus primus numerus est minor

44
00:03:29,160 --> 00:03:31,540
erant 'trying ut aliquam.

45
00:03:31,540 --> 00:03:35,820
Nunc itaque sic interponere possumus XVI in hunc inanis socors,

46
00:03:35,820 --> 00:03:40,520
quae, memento, weve creata a moventis elementa in sort portio super

47
00:03:40,520 --> 00:03:43,340
sicut diximus occurrit.

48
00:03:43,340 --> 00:03:47,900
>> Omni jure. Nunc, quatuor habemus sorted elementa et duo Unsorted elementa.

49
00:03:47,900 --> 00:03:51,600
Sic, lets movere VIII in sorted portio est.

50
00:03:51,600 --> 00:03:55,010
Octo minus est quam XLII.

51
00:03:55,010 --> 00:03:56,940
Octo minus est quam XXIII.

52
00:03:56,940 --> 00:04:00,230
VIII XVI et minus.

53
00:04:00,230 --> 00:04:03,110
Sed maior VIII IV.

54
00:04:03,110 --> 00:04:07,280
Ita ut inter IV et VIII inserere libet XVI.

55
00:04:09,070 --> 00:04:13,650
Et nunc nos iustus have unus plus elementum reliquit exstat - in XV.

56
00:04:13,950 --> 00:04:16,589
Quindecim minus est quam XLII,

57
00:04:16,589 --> 00:04:19,130
Quindecim minus est quam XXIII.

58
00:04:19,130 --> 00:04:21,750
XV et XVI minor.

59
00:04:21,750 --> 00:04:24,810
Sed XV maior est quam VIII.

60
00:04:24,810 --> 00:04:27,440
>> Sic, hic est qua nos facere volunt, etiam finalis insertionem.

61
00:04:28,770 --> 00:04:30,330
Et nos 'perfectus.

62
00:04:30,330 --> 00:04:33,540
Unsorted elementa non sunt nobis plus parte

63
00:04:33,540 --> 00:04:36,670
et nostra sorted portio est in recta ordinem.

64
00:04:36,670 --> 00:04:40,270
Minima maximaque ex ordine numerorum.

65
00:04:40,270 --> 00:04:44,330
Sic, lets 'take a inviso nonnullus pseudocode describit, gressus nos iustus patrarentur.

66
00:04:46,760 --> 00:04:51,740
>> I lineam, quid erimus scimus quia in singulari numero REDDO

67
00:04:51,740 --> 00:04:57,060
excepto primo, quia prima pars elementum ipsum sit Unsorted

68
00:04:57,060 --> 00:05:00,220
primum elementum in sorted portio est.

69
00:05:00,220 --> 00:05:06,320
II et III in lineis, Nunc sumus in Unsorted parte vestigia retinens.

70
00:05:06,320 --> 00:05:10,450
Elementum repraesentat numerus sumus currently movendo in sorted portionem,

71
00:05:10,450 --> 00:05:15,600
et j repraesentat noster index in Unsorted portio est.

72
00:05:15,600 --> 00:05:20,980
>> In linea IV, erant 'iterando per sorted portio a dextro ad sinistrum.

73
00:05:20,980 --> 00:05:26,010
Nos volo ut subsisto iterando semel elementum ad sinistram nostri nunc positio

74
00:05:26,010 --> 00:05:30,050
minus dum sumus elementum aliquam.

75
00:05:30,050 --> 00:05:35,600
In linea V, erant 'Remotio quodlibet elementum nos congressus unum spatium ad dextrum.

76
00:05:35,600 --> 00:05:40,950
Sic cum puteus clare videmus primum elementum spatii inseres

77
00:05:40,950 --> 00:05:44,080
minus quam elementum erant 'moveris.

78
00:05:44,080 --> 00:05:50,800
In linea VI, erant 'adaequationis nostri contra pergunt moveri reliquit per sorted portio est.

79
00:05:50,800 --> 00:05:56,860
Tandem acies VII, commemorati sumus pars digestus in elementum lacus.

80
00:05:56,860 --> 00:06:00,020
>> Scimus ut suus 'okay inserere in sedem j,

81
00:06:00,020 --> 00:06:05,360
quia ibi iam motus spatii elementum sit amet elit.

82
00:06:05,360 --> 00:06:09,460
Memento quod sumus commoda moveri a dextra in sinistram partem,

83
00:06:09,460 --> 00:06:13,960
sed erant 'movens per Unsorted pars a sinistra ad dextram.

84
00:06:13,960 --> 00:06:19,090
Omni jure. Lets nunc take a inviso quam diu cursus ut algorithm accepit.

85
00:06:19,090 --> 00:06:25,300
Primus certe hic quaesivit algorithm quamdiu currere pro maxima est.

86
00:06:25,300 --> 00:06:29,040
Recole quod nos repraesentare hoc currit tempore cum Big O notatio.

87
00:06:32,530 --> 00:06:38,500
In ordine exstat nostrum album, habuimus ad RESUMO super elementa in Unsorted portionem,

88
00:06:38,500 --> 00:06:43,430
et singulorum elementorum, quae sunt in potentia super omnia commoda pars.

89
00:06:43,430 --> 00:06:47,950
Intuitive, hoc sonos quasi O (n ^ II) operationem.

90
00:06:47,950 --> 00:06:51,840
>> Vultus procul nostrum pseudocode habemus loop habitant intra ansam veniat,

91
00:06:51,840 --> 00:06:55,290
quod quidem sonat, quasi Deus (II ^ n) opus.

92
00:06:55,290 --> 00:07:01,590
Tamen sorted portionem list non continebant totam list usque ad finem.

93
00:07:01,590 --> 00:07:06,920
Adhuc, possemus potentia inserere novum elementum in ipso principio de sorted portio

94
00:07:06,920 --> 00:07:09,320
in omni iteratione de algorithm,

95
00:07:09,320 --> 00:07:14,500
id quod in praesenti commoda singulari debuit portione spectare.

96
00:07:14,500 --> 00:07:20,090
Sic, ut opes possemus potentia faciunt unum comparatione pro secunda elementum,

97
00:07:20,090 --> 00:07:24,660
pro tertia pars duas comparationes, etc.

98
00:07:24,660 --> 00:07:32,480
Itaque ingressus est summa universi numeri integri a minus albo in longitudinem I I.

99
00:07:32,480 --> 00:07:35,240
Possumus hanc repraesentent cum summationem.

100
00:07:41,170 --> 00:07:47,270
>> Summationes non ingredietur, sed hoc fit aequalis summa

101
00:07:47,270 --> 00:07:57,900
n (n - I) e II, quod aequivalet n ^ II / II - n / II.

102
00:07:57,900 --> 00:08:00,800
Quando loquitur de asymptotici runtime,

103
00:08:00,800 --> 00:08:05,170
hoc n ^ II terminus est iens ut dominari hoc n term.

104
00:08:05,170 --> 00:08:11,430
Sic, insertionem generis est Big O (n ^ II).

105
00:08:11,430 --> 00:08:16,150
Quid si cucurrit insertionem hujusmodi in iam sorted list.

106
00:08:16,150 --> 00:08:20,960
Ita sistere pars a sinistra in dextram commoda tantum aedificat.

107
00:08:20,960 --> 00:08:25,050
Unde oportet quod ordinem voltis gradus n.

108
00:08:25,050 --> 00:08:29,740
>> Id est insertionem talis habet a optimus-casu perficientur n,

109
00:08:29,740 --> 00:08:34,130
quae nos repraesentant cum Ω (n).

110
00:08:34,130 --> 00:08:36,190
Quod ut 'eam propter insertionem modi,

111
00:08:36,190 --> 00:08:40,429
iustus unus multorum algorithms uti possumus exstat a album.

112
00:08:40,429 --> 00:08:43,210
Est nomen meum Tommy, et hoc est CS50.

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

114
00:08:46,110 --> 00:08:49,230
O iusta non debet aliquando incipit.

115
00:09:01,620 --> 00:09:04,760
Oh, fecimus quod - >> BUTIO!