[Powered by Google Translate] [Inserción Ordigi]
[Tommy MacWilliam] [Universitato Harvard]
[Jen CS50.TV]
Ni rigardu inserción varo, algoritmo por preni listo de nombroj kaj ordigi ilin.
Algoritmo, memoru, estas simple iom post paŝo proceduro por plenumi taskon.
La baza ideo malantaŭ inserción varo, estas dividi nian liston en du partojn,
a ordo parton kaj unsorted parton.
>> Je ĉiu paŝo de la algoritmo, numero estas movita
de la unsorted porcion al la ordo parto
ĝis fine la tuta listo estas ordigita.
Jen la listo de ses unsorted nombroj - 23, 42, 4, 16, 8, kaj 15.
Ekde ĉi tiuj nombroj estas ne ĉiuj en suprenira ordo, ili estas Unsorted.
Kiel ni ne komencis ordigi tamen, ni konsideras la ses elementoj nia unsorted parton.
>> Iam ni komencu ordigi, ni metos ĉi tiujn ordo numerojn al la maldekstra de tiuj.
Do, ni komencu kun 23, la unua elemento de nia listo.
Ni ne havas elementojn en niaj ordo parto tamen,
do ni simple konsideras 23 al esti la komenco kaj fino de nia ordo parton.
Nun, nia ordo parto havas unu nombro, 23,
kaj nia unsorted parto havas tiuj kvin nombroj.
Ni nun enigi la sekvan numeron de nia unsorted porcion, 42, en la ordo parton.
>> Por tion fari, ni bezonos kompari la 42 al la 23 - la sola elemento en nia ordo parto ĝis nun.
Kvardek du estas pli granda ol 23, do ni povas simple aldonas 42 ĝis la fino
de la ordo parton de la listo. Bonega!
Nun nia ordo parto havas du elementoj, kaj nia unsorted parto havas kvar elementoj.
Do, ni nun movi al la 4, la sekva elemento en la unsorted parton.
Do, kie devus ĉi loki en la ordo parton?
>> Memoru, ni volas meti tiun ciferon en ordo ordo
Tiel niaj ordo parto restas ĝuste ordo en ĉiu momento.
Se ni metas la 4 al la rajto de la 42, tiam nia listo estos el ordo.
Do, ni daŭrigu movas dekstren-al-maldekstra en nia speco parton.
Kiel ni movas, ni ŝanĝi ĉiun numeron malsupren lokon por lasi spacon por la nova numero.
Konsentite, 4 estas ankaŭ malpli ol 23, do ni ne povas meti ĝin ĉi tie ankaŭ ne.
Ni movi la 23 gxustan lokon.
>> Tio signifas ke ni volas meti la 4 en la unua fendo en la ordo parton.
Rimarku kiel ĉi spacon en la listo jam malplena,
ĉar ni estis movanta ordo elementoj suben kiel ni renkontis ilin.
Bone. Do, ni estas duonvoje tie.
Ni daŭrigos nian algoritmon per enmeto de la 16 en la ordo parton.
Dek ses estas malpli ol 42, do ni ŝanĝi la 42 al la rajto.
Dek ses estas ankaŭ malpli ol 23, do ni ankaŭ ŝanĝi tiu elemento.
>> Nun, 16 estas pli granda ol 4. Do, ĝi aspektas kiel ni ŝatus enmeti la 16 inter la 4 kaj la 23.
Dum movante tra la ordo parton de la listo de dekstra al maldekstra,
4 estas la unua numero ni vidis, ke estas pli malgranda ol la nombro
ni provas enmeti.
Do, nun ni povas enigi la 16 en tiun malplenan fendo,
kiu, memoru, ni kreis per movanta elementoj en la varo parton super
kiel ni renkontis ilin.
>> Bone. Nun, ni havas kvar ordo elementoj kaj du unsorted elementoj.
Do, ni movos la 8 en la ordo parton.
Ok estas malpli ol 42.
Ok estas malpli ol 23.
Kaj 8 estas malpli ol 16.
Sed 8 estas pli granda ol 4.
Do, ni ŝatus enmeti la 8 inter la 4 kaj la 16.
Kaj nun ni nur havas unu malpli ero lasis ordigi - la 15.
Dek kvin estas malpli ol 42,
Dek kvin estas malpli ol 23.
Kaj 15 estas malpli ol 16.
Sed 15 estas pli granda ol 8.
>> Do, jen kie ni volas fari nia fina inserción.
Kaj ni faris.
Ni havas ne pli elementoj en la unsorted parton,
kaj nia ordo parto estas en la korekta ordo.
La nombroj estas ordigitaj de plej malgranda al granda.
Do, ni rigardu iujn _pseudocode_ kiu priskribas la paŝojn ni simple ludado.
>> Sur la linio 1, oni povas vidi, ke ni bezonos ankaŭ persisti super ĉiu elemento en la listo
krom la unua, ĉar la unua elemento en la unsorted parton simple fariĝis
la unua elemento en la ordo parton.
Sur linioj 2 kaj 3, ni konservanta trako de nia nuna loko en la unsorted parton.
Elemento reprezentas la numeron ni aktuale movante en la ordo parton,
kaj j reprezentas nian indekson en la unsorted parton.
>> On line 4, ni ripetanta tra la ordo parton de dekstra al maldekstra.
Ni volas halti ripetanta fojon la elemento al la maldekstra de nia aktuala pozicio
estas malpli ol la elemento ni provas enmeti.
Sur la linio 5, ni sxangxigxantaj ĉiu elemento, ni renkontas unu spacon por la rajto.
Tiel, ni havos klaran spacon por enmeti en kiam ni trovas la unuan elementon
malpli ol la elemento ni moviĝas.
Sur la linio 6, ni ĝisdatigi nian nombrilo daŭrigi movi lasis tra la ordo parton.
Fine, la linio 7, ni enmeto de la elemento en la ordo parton de la listo.
>> Ni scias ke ĝi estas bone por enmeti en pozicio j,
ĉar ni jam movis la elemento kiu kutimis esti tie unu spacon por la rajto.
Memoru, ni movi tra la ordo parton de dekstra al maldekstra,
sed ni movi tra la unsorted parton de maldekstre al dekstre.
Bone. Ni nun rigardu kiel longe kurante ke algoritmo prenita.
Ni unue demandi la demandon kiom da tempo necesas por ĉi tiu algoritmo por kuri en la plej malbona kazo.
Memori, ke ni reprezentas ĉi rula tempo kun Granda a skribmaniero.
Por ordigi nian liston, ni havis ankaŭ persisti super la elementoj en la unsorted parton,
kaj por ĉiu el tiuj elementoj, potenciale super ĉiuj elementoj en la ordo parton.
Intuicie, ĉi sonojn kiel O (n ^ 2) operacio.
>> Rigardante nian _pseudocode_, ni havas buklo anidado ene alia buklo,
kiuj ja sonas kiel O (n ^ 2) operacio.
Tamen, la ordo porcion de listo ne enhavis la tutan liston ĝis la fino.
Tamen ni povus potenciale enigi novan elementon al la komenco de la ordo parto
sur ĉiu ripeto de la algoritmo,
kio signifas, ke ni devus rigardi ĉiu ero aktuale en la ordo parton.
Do, tio signifas ke ni povus potenciale fari komparon por la dua ero,
du komparoj por tria elemento, kaj tiel plu.
Do, la tuta kvanto de paŝoj estas la sumo de la entjeroj de 1 al la longo de la listo minus 1.
Ni povas reprezenti ĉi kun sumado.
>> Ni ne iros al sumadoj, sumadas tie, sed ĝi rezultas ke tiu sumado estas egala al
n (n - 1) super 2, kiu estas ekvivalenta n ^ 2/2 - n / 2.
Kiam parolante pri asimptota runtime,
ĉi n ^ 2 terminon tuj regi tiun n termino.
Do, inserción varo estas Granda O (n ^ 2).
Kio se ni kuris inserción speco sur jam ordo listo.
En tiu kazo, ni havus simple konstrui la ordo parton de maldekstre al dekstre.
Do, ni nur bezonas de la ordo de n paŝoj.
>> Tio signifas ke inserción speco havas pli okazo agado de n,
kiuj ni reprezentas kun Ω (n).
Kaj tio estas por inserción varo,
nur unu el la multaj algoritmoj povas uzi por ordigi liston.
Mia nomo estas Tommy, kaj ĉi tiu estas CS50.
[CS50.TV]
Ho, vi simple ne povas ĉesi, ke iam ĝi komenciĝas.
Ho, ni faris tion - >> Eksplodo!