[Powered by Google Translate] [Invoeging Sorteer]
[Tommy MacWilliam] [Harvard Universiteit]
[Dit is CS50.TV]
Kom ons neem 'n blik op die invoeging soort, 'n algoritme vir die neem van 'n lys van getalle en sorteer hulle.
'N algoritme, onthou, is eenvoudig 'n stap-vir-stap proses vir die totstandbrenging van 'n taak.
Die basiese idee agter die invoeging soort, is ons lys te verdeel in twee gedeeltes,
'n gesorteer gedeelte en 'n ongesorteerde gedeelte.
>> By elke stap van die algoritme, is 'n aantal verskuif
van die ongesorteerde gedeelte aan die gesorteerde gedeelte
totdat uiteindelik die hele lys is gesorteer.
Hier is die lys van ses ongesorteerde getalle - 23, 42, 4, 16, 8 en 15.
Aangesien hierdie getalle is nie al nie in stygende volgorde, hulle ongesorteerde data.
Want ons het nie begin sorteer nog nie, sal ons al ses elemente oorweeg ons ongesorteerde gedeelte.
>> Sodra ons begin sorteer, sal ons hierdie gesorteer nommers aan die linkerkant van hierdie.
So, laat ons begin met 23, die eerste element in ons lys.
Ons het nie enige elemente in ons gesorteer gedeelte nie,
so laat ons oorweeg net 23 aan die begin en einde van ons gesorteer gedeelte.
Nou, ons gesorteer gedeelte het 'n nommer 23,
en ons ongesorteerde gedeelte het hierdie vyf getalle.
Kom ons plaas die volgende getal in ons ongesorteerde gedeelte, 42, in die gesorteerde gedeelte.
>> Om dit te doen, sal ons nodig het om die 42 te vergelyk aan die 23 - tot dusver die enigste element in ons gesorteer gedeelte.
Twee-en-veertig is groter as 23 is, sodat ons kan net 42 te heg aan die einde
van die gesorteerde gedeelte van die lys. Great!
Nou ons gesorteer gedeelte het twee elemente, en ons ongesorteerde gedeelte het vier elemente.
So, laat ons beweeg nou na die 4, die volgende element in die ongesorteerde gedeelte.
So, waar moet dit geplaas word in die gesorteerde gedeelte?
>> Onthou, ons wil hierdie nommer te plaas in gesorteer einde
sodat ons gesorteer gedeelte bly korrek gesorteer ten alle tye.
As ons plaas die 4 aan die regterkant van die 42, dan sal ons lys uit van orde.
So, laat ons voortgaan om regs na links te beweeg in ons soort gedeelte.
Soos ons beweeg, laat ons skuif elke nommer 'n plek af om plek te maak vir die nuwe nommer.
Okay, 4 is ook minder as 23, so ons kan nie plaas dit hier nie.
Kom ons beweeg die 23 regte een plek.
>> Dit beteken dat ons wil die 4 in die eerste slot in die gesorteerde gedeelte te plaas.
Let op hoe hierdie ruimte in die lys wat reeds leeg was,
want ons het beweeg gesorteer elemente as ons teëgekom het.
Alles reg. So, ons is halfpad daar.
Laat ons voortgaan om ons algoritme deur die invoeging van die 16 in die gesorteerde gedeelte.
Sestien minder as 42 is, so laat ons skuif die 42 aan die regterkant.
Sestien is ook minder as 23, so laat ons ook daardie element verskuif.
>> Nou, 16 is groter as 4. So, dit lyk asof ons wil die 16 in te voeg tussen die 4 en die 23.
Terwyl dit beweeg deur middel van die gesorteerde gedeelte van die lys van regs na links,
4 is die eerste getal wat ons gesien het wat kleiner is as die aantal
ons probeer om in te voeg.
So, nou het ons kan die 16 voeg in hierdie leë slot,
wat onthou, het ons geskep deur bewegende elemente in die soort gedeelte oor
as ons teëgekom het.
>> Alles reg. Nou, ons het vier gesorteer elemente en twee ongesorteerde elemente.
So, laat ons skuif die 8 in die gesorteerde gedeelte.
Agt is minder as 42.
Agt is minder as 23.
En 8 is minder as 16.
Maar 8 is groter as 4.
So, wil ons graag die 8 tussen die 4 en die 16 in te voeg.
En nou, ons het net een element meer links te sorteer - 15.
Vyftien is minder as 42,
Vyftien is minder as 23.
En 15 is minder as 16.
Maar 15 is groter as 8.
>> So, hier is waar ons wil ons finale invoeging te maak.
En ons klaar is.
Ons het nie meer elemente in die ongesorteerde gedeelte,
en ons gesorteer gedeelte is in die korrekte volgorde.
Die getalle bestel word van die kleinste tot die grootste.
So, kom ons neem 'n blik op sommige pseudokode wat beskryf die stappe wat ons net uitgevoer.
>> Op lyn 1, kan ons sien dat ons nodig het om te itereer oor elke element in die lys
behalwe die eerste, sal net sedert die eerste element in die ongesorteerde gedeelte
die eerste element in die gesorteerde gedeelte.
Op die lyne 2 en 3, is ons die dop van ons huidige plek in die ongesorteerde gedeelte.
Element verteenwoordig die aantal wat ons tans in die gesorteerde gedeelte beweeg,
en j verteenwoordig die indeks in die ongesorteerde gedeelte.
>> On line 4, ons iterating deur die gesorteerde gedeelte van regs na links.
Ons wil om te stop iterating sodra die element aan die linkerkant van ons huidige posisie
minder is as die element wat ons probeer om te plaas.
On line 5, ons elke element wat ons teëkom een ​​spasie aan die regterkant te skuif.
Op dié manier, sal ons 'n duidelike ruimte in te voeg in wanneer ons die eerste element
minder as die element wat ons beweeg.
On line 6, werk ons ​​counter om voort te gaan om te beweeg links deur die gesorteerde gedeelte.
Ten slotte, on line 7, ons invoeging van die element in die gesorteerde gedeelte van die lys.
>> Ons weet dat dit is okay om te voeg in posisie j,
want ons het reeds die element wat gebruik word om daar te wees een spasie aan die regterkant beweeg.
Onthou, ons beweeg deur middel van die gesorteerde gedeelte van regs na links,
maar ons is deur die ongesorteerde gedeelte van links na regs beweeg.
Alles reg. Kom ons neem 'n blik op hoe lank loop dat die algoritme het.
Ons sal eers die vraag vra hoe lank neem dit vir hierdie algoritme uit te voer in die ergste geval.
Onthou dat ons hierdie tyd met Big O notasie verteenwoordig.
Ten einde ons lys te sorteer, moes ons itereer oor die elemente in die ongesorteerde gedeelte,
en vir elk van hierdie elemente, potensieel oor al die elemente in die gesorteerde gedeelte.
Intuïtief, dit klink soos 'n O (n ^ 2) werking.
>> Soek by ons pseudokode, ons het 'n geneste lus in 'n ander lus,
wat, inderdaad, klink soos 'n O (n ^ 2) werking.
Het egter die gesorteer gedeelte van die lys bevat nie die hele lys tot die bitter einde.
Tog, ons kan potensieel voeg 'n nuwe element by die begin van die gesorteerde gedeelte
op elke iterasie van die algoritme,
wat beteken dat ons wil hê om te kyk na elke element in die gesorteerde gedeelte.
So, wat beteken dat ons moontlik kan maak 'n vergelyking vir die tweede element,
twee vergelykings vir die derde element, en so aan.
So, die totale getal van die stappe is die som van die heelgetalle van 1 tot die lengte van die lys minus 1.
Ons kan verteenwoordig hierdie met 'n opsomming.
>> Ons sal nie gaan in die opsommings hier, maar dit blyk dat hierdie opsomming is gelyk aan
N (n - 1) oor 2, wat gelykstaande is n ^ 2/2 - n / 2.
Wanneer praat oor die asimptotiese runtime,
hierdie n ^ 2 termyn gaan hierdie n term te oorheers.
So, invoeging soort Big O (n ^ 2).
Wat gebeur as ons hardloop die invoeging soort op 'n reeds gesorteerde lys.
In daardie geval, ons wil net die opbou van die gesorteerde gedeelte van links na regs.
So, ons sal net op die einde van n stappe nodig.
>> Dit beteken dat die invoeging soort het 'n beste-geval prestasie van n,
wat ons met Ω (n).
En dit is die vir invoeging soort,
net een van die vele algoritmes wat ons kan gebruik om 'n lys te sorteer.
My naam is Tommy, en dit is CS50.
[CS50.TV]
O, jy kan net nie ophou dat wanneer dit begin.
O, ons het dit gedoen - >> Boom!