[Powered by Google Translate] [Insertio Sort]
[Tommy MacWilliam] [Harvard University]
[Hoc est CS50.TV]
Lets 'take a inviso insertionem modi, an algorithm pro captus a album numerorum et voluptua eos.
Algorithm est memoria, ratio perficiendi GRADATUS simpliciter opus.
Basic idea post insertionem modi, est dividere nostrum album in duas portiones,
a sorted partem et an Unsorted portio est.
>> Quolibet gradu algorithm numerus motus
a Unsorted partem sorted portio
donec eventually totius album est sorted.
Hic numerus numero sex Unsorted - XXIII, XLII, IV, XVI, VIII et XV.
Quia hi numeri non sunt omnes in ascendendo ordo, erant 'Unsorted.
Quoniam sumus non inchoatur voluptua tamen, puteus 'considerare de omnibus sex elementa nostri Unsorted portio est.
>> Quondam nos satus voluptua, puteus 'mitte illas sorted numeris ad sinistram ex istis.
Itaque XXIII principium est primum in elementum lacus.
Non habemus cuiusquam elementi in nostra sorted portio tamen,
sic lets simpliciter considerare XXIII esse initium et finis nostrae sorted portio est.
Sed ille nostrae pars commoda numero XXIII,
et nostra Unsorted pars his quinque numerorum.
Lets nunc inserere postero numerus in nostra Unsorted portionem, XLII, in sorted portio est.
>> Id est, ad opust XXIII conferre XLII - digestus in partem unam tantum materiam.
XXIII amplius quadraginta duae, additis XLII possumus ad hoc duntaxat
de sorted portio list. Magna!
Autem noster sorted pars duo elementa, et nostra Unsorted pars quatuor elementa.
Itaque Nunc IV feratur ad proxima pars Unsorted elementum.
Proinde ubi, debet hoc poni in sorted portio?
>> Recordare, nos volo ut pone istud numerum in sorted ordinem
ita noster sorted relictaque portione recte sorted in omni tempore.
XLII Si autem rectum IV ponimus, ex quo tunc erunt nomina.
Sic, lets perseverant movendo ius-ut-remansisset in sort portio est.
Sicut et nos movere, lets amoveo quisque numerus descendit locum ad locum faciunt novus enim numerus.
Bene, quam etiam IV XXIII, ita neque hic locus non est.
Lets movere XXIII ius unum locum.
>> Ut opes wed 'amo ut ponunt IV in primum socors in sorted portio est.
Ecce ut iam vacuo spatio album,
quia nos Ive 'been movendo sorted elementa down ut weve occurrit.
Omni jure. Sic, sumus ultro insequuntur ibi.
Lets pergere algorithm inserendo XVI in sorted portio est.
XLII sex minus, ita nec ad ius transferre XLII.
Sedecim etiam minor est XXIII, sic fiat scriptor etiam amoveo qui elementum.
>> Sed maior IV XVI. Ergo videtur quod libet interponere inter IV et XVI XXIII.
Dum movens per sorted portio list a dextro ad sinistrum,
IV vidi numerus primus numerus est minor
erant 'trying ut aliquam.
Nunc itaque sic interponere possumus XVI in hunc inanis socors,
quae, memento, weve creata a moventis elementa in sort portio super
sicut diximus occurrit.
>> Omni jure. Nunc, quatuor habemus sorted elementa et duo Unsorted elementa.
Sic, lets movere VIII in sorted portio est.
Octo minus est quam XLII.
Octo minus est quam XXIII.
VIII XVI et minus.
Sed maior VIII IV.
Ita ut inter IV et VIII inserere libet XVI.
Et nunc nos iustus have unus plus elementum reliquit exstat - in XV.
Quindecim minus est quam XLII,
Quindecim minus est quam XXIII.
XV et XVI minor.
Sed XV maior est quam VIII.
>> Sic, hic est qua nos facere volunt, etiam finalis insertionem.
Et nos 'perfectus.
Unsorted elementa non sunt nobis plus parte
et nostra sorted portio est in recta ordinem.
Minima maximaque ex ordine numerorum.
Sic, lets 'take a inviso nonnullus pseudocode describit, gressus nos iustus patrarentur.
>> I lineam, quid erimus scimus quia in singulari numero REDDO
excepto primo, quia prima pars elementum ipsum sit Unsorted
primum elementum in sorted portio est.
II et III in lineis, Nunc sumus in Unsorted parte vestigia retinens.
Elementum repraesentat numerus sumus currently movendo in sorted portionem,
et j repraesentat noster index in Unsorted portio est.
>> In linea IV, erant 'iterando per sorted portio a dextro ad sinistrum.
Nos volo ut subsisto iterando semel elementum ad sinistram nostri nunc positio
minus dum sumus elementum aliquam.
In linea V, erant 'Remotio quodlibet elementum nos congressus unum spatium ad dextrum.
Sic cum puteus clare videmus primum elementum spatii inseres
minus quam elementum erant 'moveris.
In linea VI, erant 'adaequationis nostri contra pergunt moveri reliquit per sorted portio est.
Tandem acies VII, commemorati sumus pars digestus in elementum lacus.
>> Scimus ut suus 'okay inserere in sedem j,
quia ibi iam motus spatii elementum sit amet elit.
Memento quod sumus commoda moveri a dextra in sinistram partem,
sed erant 'movens per Unsorted pars a sinistra ad dextram.
Omni jure. Lets nunc take a inviso quam diu cursus ut algorithm accepit.
Primus certe hic quaesivit algorithm quamdiu currere pro maxima est.
Recole quod nos repraesentare hoc currit tempore cum Big O notatio.
In ordine exstat nostrum album, habuimus ad RESUMO super elementa in Unsorted portionem,
et singulorum elementorum, quae sunt in potentia super omnia commoda pars.
Intuitive, hoc sonos quasi O (n ^ II) operationem.
>> Vultus procul nostrum pseudocode habemus loop habitant intra ansam veniat,
quod quidem sonat, quasi Deus (II ^ n) opus.
Tamen sorted portionem list non continebant totam list usque ad finem.
Adhuc, possemus potentia inserere novum elementum in ipso principio de sorted portio
in omni iteratione de algorithm,
id quod in praesenti commoda singulari debuit portione spectare.
Sic, ut opes possemus potentia faciunt unum comparatione pro secunda elementum,
pro tertia pars duas comparationes, etc.
Itaque ingressus est summa universi numeri integri a minus albo in longitudinem I I.
Possumus hanc repraesentent cum summationem.
>> Summationes non ingredietur, sed hoc fit aequalis summa
n (n - I) e II, quod aequivalet n ^ II / II - n / II.
Quando loquitur de asymptotici runtime,
hoc n ^ II terminus est iens ut dominari hoc n term.
Sic, insertionem generis est Big O (n ^ II).
Quid si cucurrit insertionem hujusmodi in iam sorted list.
Ita sistere pars a sinistra in dextram commoda tantum aedificat.
Unde oportet quod ordinem voltis gradus n.
>> Id est insertionem talis habet a optimus-casu perficientur n,
quae nos repraesentant cum Ω (n).
Quod ut 'eam propter insertionem modi,
iustus unus multorum algorithms uti possumus exstat a album.
Est nomen meum Tommy, et hoc est CS50.
[CS50.TV]
O iusta non debet aliquando incipit.
Oh, fecimus quod - >> BUTIO!