[Powered by Google Translate] TOMMY: Idemo pogledati odabira vrste, algoritam
za uzimanje popis brojeva te ih sortirati.
Algoritam, zapamtite, je jednostavno korak-po-korak
Postupak za ostvarivanje zadatka.
Osnovna ideja iza odabira vrste je podijeliti
naš popis na dva dijela -
sortirani dio i nerazvrstani dio.
Na svakom koraku algoritma, broj je premještena iz
nerazvrstani dio na razvrstanog dijela dok na kraju
Cijeli popis sortiran.
Dakle, ovdje je popis od šest brojeva -
23, 42, 4, 16, 8, i 15.
Upravo sada je cijela lista smatra nesortirani.
Iako broj kao 16 svibanj već biti u svom točne
lokacija, naš algoritam nema načina znajući da do
Cijeli popis sortiran.
Dakle, mi ćemo razmotriti svaki broj koji će se nesortirani dok smo sortirati
to mi sami.
Znamo da želimo da popis bude u uzlaznom redoslijedu.
Tako da ćete želite izgraditi sortirani dio našeg popisa
s lijeva na desno, najmanji na najveći.
Da bi to učinili, morat ćemo pronaći minimalnu Unsorted elementa
i staviti na kraju poredani dijela.
Budući da je ovaj popis nije sortiran, jedini način da to učinite je da
pogledati svaki element u nerazvrstani dijela, prisjećajući
element koji je najniži i usporedbom
svaki element na to.
Tako smo prvo ćete pogledati 23.
Ovo je prvi element smo vidjeli, pa ćemo se sjetiti
to je kao minimum.
Sljedeća ćemo pogledati 42.
42 je veći od 23, pa 23 je još uvijek minimalna.
Sljedeća je četiri, što je manje od 23, pa ćemo se sjetiti 4
kao novi minimum.
Sljedeća je 16 koji je veći od 4, SO 4
još uvijek je minimalna.
8 je veći od 4, a 15 je veći od 4, tako da 4 mora biti
Najmanji nerazvrstani element.
Dakle, iako kao ljudi možemo odmah vidjeti da je četiri
minimalni element, naš algoritam treba pogledati
svaki nerazvrstani element, čak i nakon što smo našli 4 -
minimalni element.
Tako da sada smo pronašli minimalni element, 4, mi ćemo htjeti
ga premjestiti u sortirani dio popisa.
Budući da je ovo prvi korak, to znači da želimo staviti na 4
početak popisa.
Trenutno 23 je na početku popisa, tako
ajmo zamijeniti 4 i 23.
Dakle, sada naš popis izgleda ovako.
Mi znamo da je 4 moraju biti u svojoj konačnoj lokaciji, jer je to
i najmanji element i element na početku
popisa.
Dakle, to znači da mi ne zatreba da ga ponovno pokrene.
Tako ćemo ponoviti ovaj postupak za dodavanje drugog elementa na
sortirani dio popisa.
Mi znamo da ne trebamo gledati na 4, jer je
već riješeno.
Dakle, možemo početi na 42, što ćemo se sjetiti kako se
minimalni element.
Dakle, sljedeći ćemo gledati na 23 što je manje od 42, pa smo
sjećam 23 je novi minimalno.
Zatim smo vidjeli 16 što je manje od 23, pa
16 je novi minimalno.
Sada gledamo 8 što je manje od 16, pa
8 je nova minimalna.
I na kraju 8 je manje od 15, tako da smo znali da je osam minimalna
nerazvrstani element.
Dakle, to znači da bismo trebali dodati 8 do razvrstani
dio popisa.
Upravo sada 4 je samo razvrstani element, tako želimo staviti
8 pored 4.
Budući 42 prvi element u nerazvrstani dijela od
Popis ćemo žele zamijeniti 42 i 8.
Dakle, sada naš popis izgleda ovako.
4 i 8 predstavljaju sortirani dio popisa i
Preostali brojevi predstavljaju nerazvrstani
dio popisa.
Tako ćemo nastaviti s drugom iteraciji.
Mi smo započeli sa 23 ovaj put, jer mi ne treba gledati na
je 4 i 8 više, jer oni '
već riješeno.
16 je manje od 23, pa ćemo se sjetiti
16 kao novi minimum.
16 je manji od 42, ali 15 je manje od 16, pa 15 moraju biti
Minimalna nerazvrstani element.
Dakle, sada želimo zamijeniti 15 i 23 na
dajte nam taj popis.
The sortirani dio popisa se sastoji od 4, 8 i 15, a
ti elementi još uvijek nesortirani.
No, to samo tako dogodi da sljedeći nerazvrstani element, 16,
je već riješeno.
Međutim, ne postoji način za našeg algoritma znati da 16
je već u svom pravom mjestu, tako da smo još uvijek trebaju
ponoviti točno na isti proces.
Dakle vidimo da se 16 je manje od 42, a 16 je manji od 23, pa
16 mora biti minimalno element.
To je nemoguće zamijeniti taj element sa sobom, pa možemo
jednostavno ostaviti ga u tom položaju.
Dakle, trebamo jedan više loptu u naš algoritam.
42 veći od 23, tako da 23 mora biti
Minimalna nerazvrstani element.
Nakon što smo zamijenili 23 i 42, mi završiti s naša konačna
razvrstani popis -
4, 8, 15, 16, 23, 42.
Mi znamo 42 moraju biti u ispravnom mjestu, budući da je
Jedini element lijevo, te da je izbor vrsta.
Idemo sada formalizirati naše algoritam s nekim
pseudocode.
Na liniji jedan, možemo vidjeti da trebamo integrirati više
svaki element popisa.
Osim posljednjeg elementa, budući da je jedan element koji
Popis je već riješeno.
Na liniji dva, smatramo da je prvi element nerazvrstani
dio popisa biti minimalna, kao što smo učinili s našim
Na primjer, tako da imamo nešto za usporediti.
Linija tri započinje drugi petlju u kojoj smo ponoviti više
svaki nerazvrstani element.
Mi znamo da je nakon što sam iteracija je izdvojiti dio
našeg popisa mora sam elementi u njemu od svakog koraka
vrste jedan element.
Dakle, prvi nerazvrstani element mora biti u poziciji i plus jedan.
Na liniji četiri, možemo usporediti trenutni element na minimum
element koji smo do sada vidjeli.
Ako je trenutna element manji od minimuma
element, onda ćemo se sjetiti trenutni element kao nova
Minimalna na liniji pet.
Konačno, na linijama šest i sedam, možemo zamijeniti minimalno
element s prvom nerazvrstani elementa, čime
dodavanjem na poredani dio popisa.
Nakon što smo algoritam, važno pitanje koje treba postaviti
sebe kao programera je koliko dugo se to uzeti?
Mi smo prvi put ću postaviti pitanje koliko dugo to traje za to
algoritam za rad u najgorem slučaju?
Podsjetimo mi predstavljaju ovu trčanje
put s velikom O notacijom.
Da bi se utvrdilo minimalnu Unsorted element, mi
bitno je usporediti svaki element u popisu na
svaki drugi element u popisu.
Intuitivno, ovo zvuči kao O n kvadrata radu.
Gledajući naše pseudocode, mi također imaju petlju ugniježđena unutar
drugi petlja, koja doista zvuči kao O
n kvadrata radu.
Međutim, zapamtite da mi ne treba gledati preko
Cijeli popis prilikom utvrđivanja minimalne Unsorted elementa?
Nakon što smo znali da je četiri godine izdvojiti, na primjer, nismo
trebamo gledati na to opet.
Znači li to niža trčanje vremena?
Za naš popis duljine 6, morali smo napraviti pet
usporedbe za prvi element, četiri usporedbe za
Drugi element, i tako dalje.
To znači da je ukupan broj koraka je zbroj
integers od 1 na duljinu popisa minus 1.
Mi može predstavljati to sa zbrajanjem.
Nećemo ići u summations ovdje.
No, ispostavilo se da je to zbir jednak n puta
n minus 1 preko 2.
Ili ravnopravno, n kvadrat preko dva minus n preko dvije.
Kada govorimo o asimptotska izvođenja, to n kvadratna izraz
će dominirati ovaj n pojam.
Dakle, odabir vrsta je O od n na kvadrat.
Podsjetimo da je u našem primjeru, odabrana vrsta još uvijek potrebna za
provjerite je li broj koji je već razvrstani
potrebna kako bi se preselio.
Dakle, to znači da ako smo trčali odabira vrste preko već
razvrstani popis, to će zahtijevati isti broj koraka kao što je
bi kada se izvodi preko potpuno nerazvrstani popisu.
Dakle, izbor vrsta ima najboljem slučaju izvedbe n kvadrata,
koje predstavljaju omega n kvadrata.
I to je to za izbor vrste.
Samo jedan od mnogih algoritama možemo
koristiti za sortiranje popisa.
Moje ime je Tommy, a to je cs50.