[Powered by Google Translate] [Įterpiama Rūšiuoti]
[Tommy MacWilliam] [Harvardo universiteto]
[Tai CS50.TV]
Paimkime atrodo, bent įterpimo Rūšiuoti algoritmas numerių sąrašą ir rūšiavimą.
Algoritmas, atminkite, kad yra tiesiog žingsnis po žingsnio procedūrą įvykdyti užduotį.
Pagrindinė idėja už įterpimo rūšiuoti, yra suskirstyti į mūsų sąrašą į dvi dalis,
surūšiuoti dalis ir nerūšiuotų dalis.
>> Kiekvieno algoritmo žingsnyje, numeris perkeltas
nuo nerūšiuotų dalis išrūšiuotų dalis
kol galiausiai Visas sąrašas surūšiuotas.
Čia yra šešių nesurūšiuotų skaičių, sąrašas - 23, 42, 4, 16, 8, ir 15.
Kadangi šie numeriai yra ne visi, didėjančia tvarka, jie nerūšiuotų.
Kadangi mes pradėjo rūšiavimas dar, mes atsižvelgsime į visus šešių elementų mūsų nerūšiuotų dalį.
>> Kai mes pradedame rūšiavimas, mes įdėti šias surūšiuotas numerius šių kairėje.
Taigi, pradėkime 23, pirmasis elementas mūsų sąraše.
Mes neturime dar jokių mūsų rūšiuotų dalis elementus,
tad tiesiog apsvarstyti 23 veiklos pradžia ir pabaiga mūsų rūšiuotų dalį.
Dabar mūsų surūšiuoti dalis turi vieną telefono numerį, 23,
ir mūsų nerūšiuotų dalis turi šiuos penkis skaičius.
Tegul dabar įterpti kitą skaičių mūsų nerūšiuotų dalį, 42, į išrūšiuotų dalis.
>> Norėdami tai padaryti, mes reikia lyginti nuo 42 iki 23 d - vienintelis elementas mūsų rūšiuotų dalį iki šiol.
Keturiasdešimt du yra didesnis nei 23, todėl mes galime pridėti 42 iki galo
išrūšiuotų sąrašo dalį. Puiku!
Dabar mūsų surūšiuoti dalis turi du elementus ir mūsų nerūšiuotų dalis turi keturis elementus.
Taigi, tegul dabar pereiti į 4, Kitas elementas į nerūšiuotų dalis.
Taigi, kur tai turėtų būti pateikiami išrūšiuotų dalis?
>> Nepamirškite, kad mes norime šį skaičių rūšiuotų tvarka
todėl mūsų surūšiuoti dalis išlieka teisingai surūšiuoti visais laikais.
Jei mes 4 į dešinę iš 42, tada mūsų sąraše bus ne iš eilės.
Taigi, tegul toliau juda iš dešinės į kairę, į mūsų rūšiavimo dalį.
Kaip mes judėti, galime perkelti kiekvieno numerio žemyn vieta padaryti vietos naujam numeriui.
Gerai, 4, taip pat mažiau nei 23, todėl mes negalime įdėti jį čia arba.
Pereikime 23 tinkamą vieną vietą.
>> Tai reiškia, kad mes norėtume, kad į pirmą lizdą išrūšiuotų dalis 4.
Atkreipkite dėmesį, kaip tai erdvė sąraše jau buvo tušti,
nes mes jau juda surūšiuoti elementus, kaip mes susidūrėme.
Gerai. Taigi, mes pusiaukelėje.
Tegul toliau mūsų algoritmas įrašant 16 į išrūšiuotų dalis.
Šešiolika yra mažiau nei 42, todėl galime perkelti 42 į dešinę.
Šešiolika taip pat yra mažiau nei 23, tad taip pat pasikeis, kad elementas.
>> Dabar 16 yra didesnis kaip 4. Taigi, atrodo, kad mes norite įterpti tarp 4 ir 23 16.
O juda per išrūšiuotų sąrašo dalį iš dešinės į kairę,
4 yra pirmasis skaičius, mes matėme, kuris yra mažesnis, nei iš
mes bandome įterpti.
Taigi, dabar mes galime įterpti 16 į šį tuščią lizdą,
, atminkite, kad mes sukūrė judančių elementų rūšiavimo dalis virš
kaip mes susidūrėme.
>> Gerai. Dabar, mes turime keturis surūšiuoti elementus ir du nerūšiuotos elementus.
Taigi, galime judėti į išrūšiuotų dalis 8.
Aštuoni yra mažiau nei 42.
Aštuoni yra mažiau nei 23.
Ir 8 yra mažiau nei 16.
Bet 8 yra didesnis kaip 4.
Taigi, mes norėtume įterpti 8 tarp 4 ir 16.
Ir dabar mes tiesiog dar vieną elementą į kairę rūšiuoti - 15.
Penkiolika yra mažesnis kaip 42,
Penkiolika yra mažiau nei 23.
Ir 15 yra mažiau nei 16.
Bet 15 yra didesnis nei 8.
>> Taigi, čia yra, kur mes norime, kad mūsų galutinis įterpti.
Ir baigsime.
Mes neturime daugiau elementų į nerūšiuotų dalis,
ir mūsų surūšiuoti dalis yra teisinga tvarka.
Skaičiai yra rūšiuojami nuo mažiausio iki didžiausio.
Taigi, galime imtis tam tikru pseudocode, kurios apibūdina veiksmus, mes tiesiog atliekamų išvaizdą.
>> 1 eilutėje, mes galime pamatyti, kad mes jums reikia kartoti per kiekvieną elementą sąraše
į nerūšiuotų dalis pirmojo elemento, išskyrus pirmąjį, nes tiesiog tapti
pirmasis elementas išrūšiuotų dalis.
2 ir 3 linijų, mes sekti mūsų dabartinę vietą į nerūšiuotų dalis.
Elementas yra skaičių, šiuo metu juda į išrūšiuotų dalis,
ir j simbolizuoja mūsų indeksą į nerūšiuotų dalis.
>> 4 on-line, mes iteravimu per išrūšiuotų dalį iš dešinės į kairę.
Mes norime sustabdyti iteravimu kartą elemento mūsų dabartinės padėties kairėje
yra mažiau nei elemento mes bandote įterpti.
5 on-line, mes perkelti kiekvieną elementą, mes susiduriame vieną erdvę į dešinę.
Tokiu būdu, mes turime aiškią vietos įterpti į kai randame pirmasis elementas
mažiau nei elemento Mes perkelti.
6 on-line, mes atnaujiname mūsų skaitiklis toliau judėti į kairę per išrūšiuotų dalis.
Galiausiai, 7 on-line, mes įterpiant elementą į išrūšiuotų sąrašo dalį.
>> Mes žinome, kad tai gerai, kad įterpti į poziciją j,
, nes mes jau persikėlė elementas, kuris naudojamas ten būti viena erdvė į dešinę.
Nepamirškite, kad mes žengiame per išrūšiuotų dalį iš dešinės į kairę,
bet mes per nerūšiuotų dalį iš kairės į dešinę.
Gerai. Tegul dabar imtis, kaip ilgai veikia, kad algoritmas paėmė išvaizdą.
Mes pirmą kartą užduoti klausimą, kiek laiko užtruks šis algoritmas paleisti blogiausiu atveju.
Prisiminkite, kad mes atstovaujame šį veikimo laiką su Big O notacijos.
Jei norite surūšiuoti mūsų sąraše, mes turėjome, kad keistumėte į nerūšiuotas dalis elementus,
ir kiekvienas iš šių elementų, gali per visų išrūšiuotų dalis elementų.
Intuityviai, tai skamba, kaip O (n ^ 2) operacijos.
>> Žiūri mūsų pseudocode, mes turime viduje kitos linijos įdėtos kilpa,
kuri iš tikrųjų skamba kaip O (n ^ 2) operacijos.
Tačiau surūšiuoti sąrašo dalis nebuvo visą sąrašą iki pat pabaigos.
Vis dėlto, mes potencialiai gali įterpti naują elementą pačioje pradžioje išrūšiuotų dalis
ant kiekvieno algoritmo iteracija,
o tai reiškia, kad mes turėsime pažvelgti į kiekvieno elemento, šiuo metu išrūšiuotų dalis.
Taigi, tai reiškia, kad potencialiai galėtume padaryti vieną palyginimą antrą elementą,
du trečiojo elemento palyginimų, ir taip toliau.
Taigi, iš viso priemonių yra sveikųjų skaičių suma 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 apibendrinimo yra lygus
n (n - 1) per 2, kuris yra lygiavertis n ^ 2/2 - n / 2.
Kai kalbame apie asimptotinio runtime,
tai n ^ 2 terminas vyksta dominuoti, n terminą.
Taigi, įterpimas rūšiuoti Didelės O (n ^ 2).
Ką daryti, jei nubėgome įterpimo rūšiuoti jau rūšiuotų sąrašą.
Tokiu atveju, mes norime tiesiog sukurti surūšiuoti dalį iš kairės į dešinę.
Taigi, mes tik reikia n žingsnių tvarka.
>> Tai reiškia, kad,, kad įterpimo rūšiuoti geriausiu atveju našumą n,
kurią mes atstovaujame Ω (n).
Ir štai įterpimo rūšiuoti,
tik vienas iš daugelio algoritmų, mes galime naudoti rūšiuoti sąrašą.
My name is Tommy, ir tai yra CS50.
[CS50.TV]
Oh, tu tiesiog negali sustoti, kad kai jis pradeda.
O, mes padarėme, kad - >> Boom!