[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.