[Powered by Google Translate] [Ubacivanje Sortiraj]
[Tommy MacWilliam] [Sveučilište Harvard]
[Ovo je CS50.TV]
Idemo pogledati unosa vrste, algoritam za uzimanje popis brojeva te ih sortirati.
Algoritam, zapamtite, je jednostavno korak-po-korak postupak za ostvarivanje zadatka.
Osnovna ideja iza unosa vrste, je podijeliti našu listu na dva dijela,
sortirani dio i nerazvrstani dio.
>> Na svakom koraku algoritma, broj je premještena
od nerazvrstani dijela na sortirati dio
dok na kraju cijeli popis sortiran.
Ovdje je popis od šest Unsorted brojeva - 23, 42, 4, 16, 8, i 15.
Budući da ove brojke nisu svi u uzlaznom redoslijedu, oni nesortirani.
Budući da nismo počeli sortiranje još ćemo razmotriti svih šest elementima našu nerazvrstani dio.
>> Jednom smo započeli sortiranje, mi ćemo staviti ove sortirane brojeve na lijevoj strani tih.
Dakle, počnimo sa 23, prvi element u našem listu.
Mi nemamo nikakve elemente u našoj sortirani dijela ipak,
pa neka je jednostavno uzeti u obzir 23 biti početak i kraj našeg poredani dijela.
Sada, naš razvrstani dio ima jedan broj, 23,
i naš nerazvrstani dio ima tih pet brojeva.
Idemo sada umetnite sljedeći broj u našoj nerazvrstani dio, 42, u razvrstanih dijela.
>> Da biste to učinili, morat ćemo usporediti 42 do 23 - jedini element u našoj sortirani dijela tako daleko.
Četrdeset i dva je veći od 23, tako da smo jednostavno možete dodati 42 do kraja
o poredani dijela popisa. Sjajno!
Sada naša razvrstani dio ima dva elementa, a naš nerazvrstani dio ima četiri elementa.
Dakle, ajmo sad premjestiti na četiri, sljedeći element u nerazvrstani dijela.
Dakle, gdje bi trebao to biti smješteni u sortirani dio?
>> Zapamtite, mi želimo da se taj broj u sortiraju bi
tako je i naš razvrstani dio ostaje pravilno razvrstani u svim vremenima.
Ako stavite 4 desno od 42, onda naš popis će biti iz reda.
Dakle, neka je i dalje se kreće s desna na lijevo u našem sortiranja dijela.
Kao što smo premjestiti, neka je smjena svaki broj dolje na mjesto kako bi napravili mjesta za novi broj.
Ok, 4 je također manje od 23, pa ne možemo staviti ni ovdje.
Idemo na 23 pravo jednom mjestu.
>> To znači da bismo željeli staviti 4 u prvom utor u razvrstanih dijela.
Obavijest o tome kako je ovaj prostor u popisu je već bio prazan,
jer smo bili kreće sortirane elemente dolje kao što smo ih susreli.
U redu. Dakle, mi smo na pola puta.
Idemo dalje naš algoritam umetanjem 16 u razvrstanih dijela.
Šesnaest je manje od 42, pa ajmo pomaknula 42 na desnoj strani.
Šesnaest je također manje od 23, pa neka je i pomak tog elementa.
>> Sada, 16 je veći od 4. Dakle, izgleda da bih umetnuti 16 između 4 i 23.
Dok se kreće kroz poredani dio popisa s desna na lijevo,
4 je prvi broj vidjeli smo da je manji od broja
Pokušavamo umetnuti.
Dakle, sada možemo umetnuti 16 u ovom prazni utor,
koja, zapamtite, mi smo stvorili pokretnih elemenata u sortiranja dijela preko
kao što smo ih susreli.
>> U redu. Sada imamo četiri sortirane elemente i dva Unsorted elemente.
Dakle, neka je premjestiti 8 u razvrstanih dijela.
Osam je manje od 42.
Osam je manje od 23.
I 8 je manje od 16.
No 8 veći od 4.
Dakle, željeli bismo umetnuti 8 između 4 i 16.
I sada imamo samo jedan više elementa lijevo za sortiranje - The 15.
Petnaest je manje od 42,
Petnaest je manje od 23.
I 15 je manje od 16.
Ali 15 je veći od 8.
>> Dakle, ovdje je mjesto gdje želimo da naš konačni umetanje.
I mi smo gotovi.
Mi nemamo više elemenata u nerazvrstani dijela,
i naš razvrstani dio je u ispravnom redoslijedu.
Brojevi su poredani od najmanjeg do najvećeg.
Dakle, neka je pogledati neke pseudocode koji opisuje korake samo smo izvodili.
>> Na liniji 1, možemo vidjeti da ćemo morati ponoviti više svaki element u popisu
osim prve, od prvog elementa u nerazvrstani dijelu jednostavno će postati
prvi element u poredani dijelu.
Na linijama 2 i 3, mi smo praćenje naše sadašnje mjesto u nerazvrstani dijela.
Element predstavlja broj trenutno smo kreće u razvrstanog dijela,
i j predstavlja našu indeks u nerazvrstanog dio.
>> Na liniji 4, mi smo Ponavljanje kroz poredani dio s desna na lijevo.
Želimo da se zaustavi Ponavljanje jednom elementu na lijevoj strani naše trenutne pozicije
je manji od elementa Pokušavamo umetnuti.
Na liniji 5, mi smo prebacuje svaki element susrećemo jedno mjesto na desno.
Na taj način, imat ćemo jasnu prostor za umetanje u kada smo pronašli prvi element
manje od elementa krećemo.
Na liniji 6, ažurirat ćemo naš brojač nastaviti kretati lijevo kroz poredani dijela.
Konačno, na liniji 7, mi smo umetanja element u poredani dio popisa.
>> Mi znamo da je u redu da uložite u položaj j,
jer već smo se preselili element koji se koristi da se tamo jedno mjesto na desno.
Zapamtite, idemo kroz poredani dio s desna na lijevo,
ali idemo kroz nesortirani dio s lijeva na desno.
U redu. Idemo sada pogledati koliko dugo trčanje koje algoritam uzeo.
Mi smo prvi put ću postaviti pitanje koliko dugo to traje za ovaj algoritam za rad u najgorem slučaju.
Sjetite se da smo predstavljaju ovu trčanje vrijeme s Big O notacijom.
Kako bi se sortirati naš popis, morali smo ponoviti tijekom elemente u nerazvrstani dijela,
a za svaki od tih elemenata, potencijalno nad svim elementima u razvrstanih dijela.
Intuitivno, ovo zvuči kao O (n ^ 2) rada.
>> Gledajući naše pseudocode, imamo petlju ugniježđena unutar drugog kruga,
koji je, doista, zvuči kao O (n ^ 2) rada.
Međutim, razvrstani dio popisa ne sadrže cijeli popis do samog kraja.
Ipak, mi potencijalno mogao ubaciti novi element na samom početku sortirane dio
na svakom iteracija algoritma,
što znači da ćemo morati gledati na svakom elementu trenutno u razvrstanih dijela.
Dakle, to znači da smo potencijalno mogao napraviti jednu usporedbu za drugi element,
dvije usporedbe za trećeg elementa, i tako dalje.
Dakle, ukupan broj koraka je zbroj brojeva od 1 do duljine popisa minus 1.
Mi može predstavljati to sa zbrajanjem.
>> Nećemo ići u summations ovdje, ali ispada da je to zbir je jednaka
n (n - 1) više od 2, što je ekvivalent n ^ 2/2 - n / 2.
Kada govorimo o asimptotska izvođenja,
ovo n ^ 2 pojam će dominirati ovaj n pojam.
Dakle, umetanje vrsta je Big O (n ^ 2).
Što ako smo trčali unosa vrsta na već sortirane liste.
U tom slučaju, mi jednostavno bih izgraditi sortirani dio s lijeva na desno.
Dakle, mi samo trebate na red n koraka.
>> To znači da umetanje vrsta ima najbolje slučaj izvedbu n,
koje predstavljaju s Ω (n).
I to je to za umetanja vrste,
samo jedan od mnogih algoritama možemo koristiti za sortiranje popisa.
Moje ime je Tommy, a ovo je CS50.
[CS50.TV]
Oh, vi jednostavno ne možete prestati da nakon što počne.
Oh, mi to učinio - >> Bum!