[Powered by Google Translate] Tommy: Paimkime atrankoje rūšiuoti išvaizdą, algoritmas
numerių sąrašą ir rūšiavimą.
Algoritmas, atminkite, kad yra tiesiog žingsnis po žingsnio
tvarka įvykdyti užduotį.
Pagrindinė idėja atrankos rūšiuoti yra suskirstyti
mūsų sąrašą į dvi dalis -
surūšiuoti dalis ir nerūšiuotų dalis.
Kiekvieno algoritmo žingsnyje, numeris bus perkeltas iš
nerūšiuotų dalis išrūšiuotų dalis, kol galiausiai
Visas sąrašas surūšiuotas.
Taigi čia šešių numerių sąrašas -
23, 42, 4, 16, 8, ir 15.
Dabar visas sąrašas yra laikomas nerūšiuotų.
Nors kaip 16 jau gali būti jo teisingas
vieta, mūsų algoritmas neturi žinodami, kad, kol kelią
Visas sąrašas surūšiuotas.
Taigi, mes atsižvelgsime į kiekvieną numerį, kurį nerūšiuotų, kol mes rūšiuoti
tai patys.
Mes žinome, kad mes norime, sąrašas sudaromas didėjančia seka.
Taigi, mes norime sukurti surūšiuoti dalį mūsų sąraše
iš kairės į dešinę, mažiausio iki didžiausio.
Norėdami tai padaryti, mums reikia rasti mažiausią nerūšiuotų elementas
ir įdėti jį išrūšiuotų dalies pabaigoje.
Kadangi šis sąrašas nėra rūšiuojamos, vienintelis būdas tai padaryti yra
pažvelgti į kiekvieno elemento į nerūšiuotų dalis, prisimindamas
, kuris elementas yra žemiausias ir lyginant
kiekvienas elementas, kad.
Taigi, mes pirmą kartą pažvelgti į 23 d.
Tai yra pirmasis elementas, mes matėme, todėl mes prisiminti
kaip minimum.
Kitas mes pažvelgti į 42.
42 yra didesnis nei 23, todėl 23 yra dar minimalus.
Kitas yra 4, kuris yra mažesnis kaip 23, todėl mes prisiminti 4
su nauju minimaliu.
Kitas yra 16, kuris yra didesnis nei 4, SO 4
vis dar yra minimalus.
8 yra didesnis nei 4, ir 15 yra didesnis nei 4, tad 4 turi būti
mažiausias nerūšiuotų elementas.
Taigi, nors, kaip žmogui, mes galime iš karto pamatyti, kad 4 yra
minimalus elementas, mūsų algoritmas turi išnagrinėti
kas nerūšiuotų elementas, net po to, kai mes pastebėjome, 4 -
minimalus elementas.
Taigi dabar, kad mes pastebėjome, minimalų elementą, 4, mes nori
perkelti jį į išrūšiuotų sąrašo dalį.
, Nes tai yra pirmasis žingsnis, tai reiškia, kad mes norime įdėti 4
sąrašo pradžioje.
Dabar 23 yra sąrašo pradžioje, todėl
tegul apsikeitimo 4 ir 23.
Taigi dabar mūsų sąrašas atrodo taip.
Mes žinome, kad 4 turi būti savo galutinę vietą, nes ji yra
mažiausias elementas ir elementas pradžioje
iš sąrašo.
Taigi, tai reiškia, kad mes neturime kada nors reikės perkelti jį dar kartą.
Taigi leiskite pakartoti šį procesą įtraukti kitą elementą į
surūšiuoti dalis sąrašo.
Mes žinome, kad mums nereikia pažvelgti į 4, nes tai
jau surūšiuoti.
, Kad galėtume pradėti 42, kuriuos mes prisiminti, kaip
minimalus elementas.
Taigi, kitą mes pažvelgti į 23, kuris yra mažesnis nei 42, todėl mes
prisiminti 23 yra naujas minimalus.
Toliau matome 16, kuris yra mažiau nei 23, todėl
16 yra naujas minimalus.
Dabar pažvelgsime 8, kuris yra mažesnis nei 16, todėl
8 yra naujas minimalus.
Ir pagaliau 8 yra mažesnis kaip 15, todėl mes žinome, kad 8 yra minimalus
nerūśiuota elementas.
Taigi, tai reiškia, kad mes turime pridėti 8 surūšiuoti
dalis iš sąrašo.
Dabar 4 yra tik surūšiuoti elementas, todėl mes norime įdėti
8 kitas į 4.
Nuo 42 yra pirmasis elementas nerūšiuotų dalis
sąrašas, mes norime sukeisti 42 ir 8.
Taigi dabar mūsų sąrašas atrodo taip.
4 ir 8 atstovauti surūšiuoti sąrašo dalį, o
likę skaičiai atspindi nerūšiuotų
dalis iš sąrašo.
Taigi tegul toliau su kitu iteracijos.
Mes pradedame su 23 šį kartą, nes mums nereikia ieškoti
4 ir 8 nebėra, nes jie jau
jau buvo išrūšiuotos.
16 yra mažiau nei 23, todėl mes prisiminti
16 nauju minimaliu.
16 yra mažiau nei 42, bet 15 yra mažiau nei 16, kad 15 turi buti
minimalus nerūšiuotų elementas.
Taigi, dabar mes norime sukeisti 15 ir nuo 23 iki
suteikia mums šį sąrašą.
Surūšiuoti sąrašo dalis susideda iš 4, 8 ir 15, ir
šie elementai dar nerūšiuotų.
Bet jis tiesiog taip atsitinka, kad šalia nerūšiuotų elementas, 16,
jau rūšiuojamos.
Tačiau ten nėra taip, kad mūsų algoritmas žinoti, kad 16
jau teisingą vietą, todėl mes vis dar reikia
pakartoti lygiai tą patį procesą.
Taigi matome, kad 16 yra mažiau nei 42, o 16 yra mažiau nei 23, todėl
16 turi būti minimalus elementas.
Tai neįmanoma apsikeitimo šį elementą su savimi, kad galėtume
tiesiog palikite jį šioje vietoje.
Taigi, mes turime dar vieną perėją algoritmą.
42 yra didesnis nei 23, kad 23 turi būti
minimalus nerūšiuotų elementas.
Kai mes sukeisti 23 ir 42, mes galų gale su mūsų galutinis
surūšiuoti sąrašas
4, 8, 15, 16, 23, 42.
Mes žinome, 42 turi būti tinkamoje vietoje, nes tai
vienintelis elementas, į kairę, ir kad atranka rūšiuoti.
Tegul dabar oficialiai įforminti mūsų algoritmas su kai
Pseudocode.
On line vieną, mes galime pamatyti, kad turime integruoti per
kiekvienas sąrašo elementas.
Išskyrus paskutinį elementą, nes 1 elementas
sąrašas jau yra rūšiuojamos.
On line du, mes manome, kad pirmasis elementas nerūšiuotų
sąrašo dalis, kad tai yra minimalus, kaip pasielgė su mūsų
pavyzdys, todėl mes turime ką palyginti.
3 linija prasideda antrą kilpą, kurioje mes pakartoti per
kiekvienas nerūšiuotų elementas.
Mes žinome, kad po to, kai aš iteracijų, surūšiuoti dalis
mūsų sąraše turi būti i elementai, nes kiekviename žingsnyje
rūšių vieną aspektą.
Taigi pirmas nerūšiuotų elementas turi būti i padėtyje plius 1.
On line keturi, mes palyginti dabartinę elementas iki minimumo
elementas, kad mes matėme iki šiol.
, Jei dabartinis elementas yra mažesnis nei minimalus
elementas, tada mes prisimename dabartinį elementą kaip nauja
minimalus 5 on-line.
Galiausiai, šešių ir septynių linijų, apsikeitimo mažiausiai
su pirmuoju nerūšiuotų elemento elementas, tokiu būdu
pridedant jį prie išrūšiuotų sąrašo dalį.
Kai mes turime algoritmą, svarbus klausimas paklausti
save programuotojais, kiek laiko tai užtruks?
Mes pirmą kartą užduoti klausimą, kiek laiko užtruks šis
algoritmas paleisti blogiausiu atveju?
Prisimenu, mes atstovaujame šį skaičiavimą
laikas su Big O notacijos.
, Siekiant nustatyti minimalų nerūšiuotų elementą, mes
iš esmės buvo palyginti kiekvieną elementą sąraše
kiekvienas kitas elementas sąraše.
Intuityviai, tai, pavyzdžiui, n kvadrato operacijos O garsai.
Žiūri mūsų pseudocode, mes taip pat turime kilpa įdėtos viduje
kita kilpa, kuri iš tikrųjų skamba tarsi O
iš n kvadrato operacijos.
Tačiau atminkite, kad mes ne reikia ieškoti per
visą sąrašą, nustatant minimalų nerūšiuotų elementą?
Kai mes žinojome, kad 4 buvo rūšiuojami, pavyzdžiui, mes ne
reikia dar kartą pažvelgti į jį.
Taigi ar tai mažesnė veikimo laiką?
Dėl mūsų sąraše ilgis 6, mums reikia padaryti 5
palyginimų pirmojo elemento, keturi palyginimų
Antrasis elementas, ir taip toliau.
Tai reiškia, kad priemonių yra iš viso suma
sveikieji skaičiai nuo 1 iki sąrašo ilgio minus 1.
Mes galime atstovauti tai su sumavimo.
Mes negalime eiti į summations čia.
Tačiau paaiškėja, kad tai sumavimas yra lygus n kartų
n atėmus 1 per 2.
Arba analogiškai n kvadrato per 2 minus n per 2.
Kai kalbame apie asimptotinio runtime, tai n kvadrato terminas
vyksta dominuoti, n terminą.
Taigi pasirinkimas rūšiuoti yra O n kvadrato.
Prisiminkite, kad mūsų pavyzdyje, atranka tarsi vis dar reikia
patikrinti, ar numeris, kuri jau buvo surūšiuoti
reikia būti perkeltas.
Taigi, tai reiškia, kad jei mes per jau vyko atrankos rūšiuoti
surūšiuoti sąrašą, jam reikėtų tą patį skaičių priemonių, kurias jis
būtų važiuojant visiškai nerūšiuotų sąrašo.
Taigi pasirinkimas rūšiuoti yra geriausiu atveju atlikimą n kvadrato,
kurią mes atstovaujame su omega n kvadrato.
Ir štai Pasirinkimo rūšiuoti.
Tik vienas iš daugelio algoritmų, mes galime
rūšiuoti sąrašą.
My name is Tommy, ir tai yra CS50.