[Powered by Google Translate] Tommy: Kom ons neem 'n blik op die seleksie soort, 'n algoritme
vir die neem van 'n lys van getalle en sorteer hulle.
'N algoritme, onthou, is eenvoudig 'n stap-vir-stap
prosedure vir die totstandbrenging van 'n taak.
Die basiese idee agter die seleksie soort is te verdeel
ons lys in twee gedeeltes
'n gesorteer gedeelte en 'n ongesorteerde gedeelte.
By elke stap van die algoritme, is 'n aantal verskuif vanaf die
ongesorteerde gedeelte na die gesorteerde gedeelte totdat uiteindelik die
hele lys is gesorteer.
So hier is 'n lys van ses nommers -
23, 42, 4, 16, 8, en 15.
Nou die hele lys word beskou as ongesorteerde data.
Selfs al is 'n aantal soos 16 kan reeds in die korrekte
plek, ons algoritme het geen manier om te weet dat, totdat die
hele lys is gesorteer.
So ons sal elke nommer ongesorteerde oorweeg word totdat ons sorteer
dit self.
Ons weet dat ons wil die lys te wees in stygende orde.
So ons sal wil bou aan die gesorteerde gedeelte van ons lys
van links na regs, die kleinste tot die grootste.
Om dit te doen, moet ons die minimum ongesorteerde element te vind
en sit dit aan die einde van die gesorteerde gedeelte.
Aangesien hierdie lys nie gesorteer, die enigste manier om dit te doen is om te
kyk na elke element in die ongesorteerde gedeelte, onthou
Watter element is die laagste en vergelyk
elke element dat.
So sal ons eers kyk na die 23.
Dit is die eerste element wat ons gesien het, so sal ons onthou
dit as die minimum.
Volgende sal ons kyk na 42.
42 is groter as 23, so 23 is nog steeds die minimum.
Volgende is die 4 wat is minder as 23, so ons sal onthou 4
as die nuwe minimum.
Volgende is 16 wat is groter as 4, so 4
is nog steeds die minimum.
8 is groter as 4 en 15 is groter as 4, so 4 moet
die kleinste ongesorteerde element.
So selfs al is ons as mense kan onmiddellik sien dat 4 is
die minimum element, ons algoritme nodig het om na te kyk
elke ongesorteerde element, selfs nadat ons die 4 gevind het - die
minimum element.
So nou dat ons die minimum element, 4 gevind het, sal ons wil
om dit te skuif in die gesorteerde gedeelte van die lys.
Want dit is die eerste stap, dit beteken dat ons wil 4 te stel
die begin van die lys.
Reg nou 23 is aan die begin van die lys, so
Kom ons ruil die 4 en die 23.
So nou is ons lys lyk.
Ons weet dat 4 moet in sy finale plek, want dit is
beide die kleinste element en die element aan die begin
van die lys.
Dit beteken dus dat ons nooit nodig om dit weer te beweeg.
So laat ons herhaal hierdie proses om 'n ander element te voeg aan die
gesorteer gedeelte van die lys.
Ons weet dat ons nie nodig het om te kyk na die 4, want dit is
reeds gesorteer.
Sodat ons kan begin by die 42, wat ons sal onthou as die
minimum element.
So, volgende sal ons kyk na die 23 wat minder as 42, so ons
Onthou 23 is die nuwe minimum.
Volgende sien ons die 16 wat minder is as 23, so
16 is die nuwe minimum.
Nou kyk ons ​​by die 8 wat minder is as 16, so
8 is die nuwe minimum.
En laastens 8 is minder as 15, so ons weet dat die 8 is 'n minimum
ongesorteerde element.
So dit beteken dat ons 8 voeg aan die gesorteerde
gedeelte van die lys.
Reg nou 4 is die enigste gesorteer element, so ons wil te plaas
die 8 volgende aan die 4.
Sedert 42 is die eerste element in die ongesorteerde gedeelte van die
lys, sal ons wil die 42 en die 8 te ruil.
So nou is ons lys lyk.
4 en 8 verteenwoordig die gesorteerde gedeelte van die lys, en die
oorblywende getalle verteenwoordig die ongesorteerde
gedeelte van die lys.
So laat ons voortgaan met 'n ander iterasie.
Ons begin met 23 hierdie tyd, want ons hoef nie te kyk na
die 4 en die 8 nie, want hulle het
reeds gesorteer.
16 is minder as 23, so ons sal onthou
16 as die nuwe minimum.
16 is minder as 42, maar 15 is minder as 16, so 15 moet
die minimum ongesorteerde element.
So nou het ons wil die 15 en die 23 tot te ruil
gee ons hierdie lys.
Die gesorteer gedeelte van die lys bestaan ​​uit 4, 8 en 15, en
hierdie elemente is nog steeds ongesorteerde data.
Maar dit gebeur net so dat die volgende ongesorteerde element, 16,
is reeds gesorteer.
Daar is egter geen manier vir ons algoritme om te weet dat 16
is reeds in sy regte plek, so het ons nog nodig het om te
presies dieselfde proses herhaal.
So sien ons dat 16 is minder as 42, en 16 is minder as 23, so
16 moet die minimum element.
Dit is onmoontlik om hierdie element te ruil met homself, sodat ons kan
laat dit eenvoudig in hierdie plek.
So ons moet een meer slaag van ons algoritme.
42 is meer as 23, so 23 moet wees om die
minimum ongesorteerde element.
Sodra ons ruil die 23 en die 42, eindig ons met ons finale
gesorteerde lys -
4, 8, 15, 16, 23, 42.
Ons weet 42 moet in die korrekte plek, want dit is die
enigste element is links, en dit is 'n seleksie soort.
Kom ons kyk nou formaliseer ons algoritme met 'n paar
pseudokode.
On line een, kan ons sien dat ons nodig het om te integreer oor
elke element van die lys.
Behalwe die laaste element, want die 1 element
lys is reeds gesorteer.
On line twee, ons kyk na die eerste element van die unsorted
gedeelte van die lys te wees van die minimum, soos ons gedoen het met ons
byvoorbeeld, so ons het iets om te vergelyk.
Lyn drie begin 'n tweede rondte wat ons itereer oor
elke ongesorteerde element.
Ons weet dat na i iterasies, die gesorteerde gedeelte
van ons lys moet ek elemente in dit sedert elke stap
vorme een element.
Dus is die eerste ongesorteerde element moet in posisie i plus 1.
On line vier ons dit vergelyk met die huidige element tot die minimum
element wat ons tot dusver gesien het.
Indien die huidige element is kleiner as die minimum
element, dan onthou ons die huidige element as die nuwe
minimum on line vyf.
Ten slotte, op die lyne ses en sewe, ruil ons die minimum
element met die eerste ongesorteerde element, en daardeur
toe te voeg aan die gesorteerde gedeelte van die lys.
Sodra ons 'n algoritme, 'n belangrike vraag te vra
onsself as programmeerders hoe lank het dit neem?
Ons sal eers die vraag vra hoe lank neem dit vir hierdie
algoritme uit te voer in die ergste geval?
Onthou ons verteenwoordig die verloop
tyd met die groot O notasie.
Ten einde die minimum ongesorteerde element te bepaal, het ons
wese het elke element in die lys te vergelyk
elke ander element in die lys.
Intuïtief, dit klink soos 'n O van n kwadraat werking.
Op soek na ons pseudokode, ons het ook 'n lus geneste binne
nog 'n lus, wat inderdaad klink soos 'n O
van n kwadraat werking.
Egter onthou dat ons nie nodig het om te kyk oor die
volledige lys by die bepaling van die minimum ongesorteerde element?
Sodra ons het geweet dat die 4 gesorteer, byvoorbeeld, ons het nie
nodig het om te kyk na dit weer.
So doen dit laer die loop van die tyd?
Vir 'n lys van lengte 6, ons nodig het vyf te maak
vergelykings vir die eerste element, vier vergelykings vir
die tweede element, en so aan.
Dit beteken dat die totale aantal 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 keer
n minus 1 oor 2.
Of gelykerwys, n oor 2 vierkant minus n oor 2.
Wanneer praat oor die asimptotiese runtime, n kwadraat term
gaan hierdie n term te oorheers.
So seleksie soort van n kwadraat O is.
Onthou dat in ons voorbeeld, seleksie soort nog nodig om te
Kontroleer of die nommer wat reeds gesorteer
wat nodig is om te verskuif word.
So dit beteken dat as ons seleksie soort gehardloop oor 'n reeds
gesorteerde lys, sou dit dieselfde aantal stappe soos dit vereis
sou wanneer jy loop oor 'n heeltemal ongesorteerde lys.
So seleksie soort het 'n beste geval prestasie van n kwadraat,
wat ons met omega n kwadraat.
En dit is dit vir keuring soort.
Net een van die vele algoritmes wat ons kan
gebruik om 'n lys te sorteer.
My naam is Tommy, en dit is cs50.