>> MARK GROZEN-SMITH: Bok, ja sam Marko Grozen-Smith, a to je Quicksort.
Baš kao što je umetanje vrste i mjehur sortiranje, Quicksort je algoritam za
sortiranje popisa ili niz stvari.
Za jednostavnost, pretpostavimo da su oni stvari su samo cijeli brojevi, ali
Znam da Quicksort radi za više nego samo brojevima.
Quickstart je malo složeniji od umetanja ili mjehurića, ali to je
također mnogo učinkovitiji u većini slučajeva.
Čekaj malo.
Je li samo reći "većina slučajevi ", a ne" sve "?
Zanimljivo, br.
Nisu svi slučajevi su isti.
Ne brinite o ovom detalju, ako vam nisu vidjeli veliki O zapis, no
Quicksort je O (n na kvadrat) algoritam u najgorem slučaju, baš kao i
umetanja ili mjehurić vrsta.
Međutim, to obično djeluje mnogo više kao stari analogni m algoritma.
Zašto?
Vratit ćemo se na to kasnije.
No, za sada, idemo samo naučiti Kako Quicksort radi.
>> Tako ćemo šetati Quicksorting to niz brojeva od najmanjeg
do najvećih.
Ovdje imamo cijeli brojevi 6, 5, 1, 3, 8, 4, 7, 9, i 2.
Prvo, mi pokupiti konačni element ovo polje - u ovom slučaju, dva -
i poziv da se "stožer." Zatim smo početi gledati na dvije stvari -
jedan, najniži indeks, koji ću uputiti kao boraveći s desne strane
zid, i, dva, lijevom element, koji ću nazvati "struje
elementa. "Ono što ćemo učiniti je izgleda sve druge elemente, druge
od pivota, i staviti sve elemente manji od pivota na
lijevo od zida i sve one veći od pivota na
Pravo na zidu.
Zatim, konačno, mi ćemo pasti stožer Pravo na tom zidu bi ga staviti između
svi brojevi manji od njega i sve veći broj.
>> Tako ćemo učiniti.
Podigni 2, staviti na zid na početku, i pozvati 6 "Current
elementa. "Na taj način želimo pogledati Naš trenutni element 6.
A budući da je veći od 2, mi ga ostaviti tamo
Pravo na zidu.
Zatim smo prešli na pogledati na 5 kao naš trenutni element i vidjeti da je to
je, opet, veći od zgloba, tako da se ostavite ga gdje se nalazi na desnoj strani
strane zida.
Mi smo krenuti dalje.
Naš trenutni element sad 1, i - oh.
Ovo je sada drugačija.
Trenutna element je sada manja od pivot, pa želimo da se stavi
s lijeve strane zida.
Da biste to učinili, neka je samo prebaciti Trenutna element s najmanjim indeksom
sjedi samo na desnoj strani zida.
Sada smo premjestiti zid do jedne indeksa do 1 je na lijevoj
strani zidu.
>> Čekaj.
Samo sam umiješan i elemente za desnoj strani zida, zar ne?
Ne brinite.
To je u redu.
Jedino što mi je stalo, za sada je da su svi ti elementi
Pravo na zidu su veće od pivota.
No stvarni poredak pretpostavlja još.
>> Sada, natrag na sortiranje.
Dakle, mi i dalje gleda na Ostatak elemenata.
I u ovom slučaju, vidimo da postoje nema druge elemente manje od
pivot, tako da smo ih sve ostaviti na desna strana zida.
Konačno, možemo doći do trenutnog elementa i vidjeti da je pivot.
Sada, to znači da imamo dva dijelovi polja, prvi je bio
Mali na pivota, a na lijevoj strani zida, a drugom biću
veći od pivota na desnoj strani zida.
Mi želimo staviti pivot element između dva, a onda ćemo znati
da Zglob je u pravu Konačna sortirani mjesto.
Tako smo prebacili prvi element na desna strana zida sa osovinom,
a znamo pivot-a u pravilnom položaju.
>> Zatim smo ponoviti ovaj postupak za subarrays lijevo i desno od pivota.
Od zadnjeg subarray je samo jedan Element dugo, znamo da je već
sortirani jer kako možete biti izvan naručiti ako ste samo jedan element?
Na desnoj strani subarray smo vidim da je pivot je 5, a zid
je samo ostalo od šest.
I trenutni element počinje kao 6.
6. tako je veća od 5.
Mi smo ga ostaviti gdje se nalazi na desnoj strani zida.
Sada se kreće na, 3 manji od 5.
Tako smo ga prebaciti s prvim elementom samo pravo na zidu.
Sada, preselio sam se u zid do jednog.
Sada se kreće na 8..
8 je veći od 5, i tako smo ga ostaviti.
4 manji od 5, pa smo ga prebacili.
I dalje.
>> Svaki put kad smo ponoviti postupak na lijeve i desne strane polja. mi
odabrati stožer i raditi usporedbe i stvoriti još jednu razinu lijevo i
pravo subarrays.
Ovaj rekurzivna poziv će se nastaviti sve dok možemo doći do kraja, kada smo
podijeljen cjelokupni niz u samo subarrays duljine 1.
Od tamo, znamo niz sortiran jer svaki element ima, na
nekom trenutku, bio pivot.
Drugim riječima, za svaki element, sve Brojevi na lijevo su manje
vrijednosti i sve brojeve zar ima veće vrijednosti.
>> Ova metoda djeluje jako dobro, ako vrijednost zakretanja odabrana
otprilike u sredini raspon vrijednosti popis.
To bi značilo da, nakon što smo premjestiti Elementi okolo, ima oko onoliko
elemenata na lijevoj pivota kao što postoje u desno.
A podjela-i-osvajanje priroda Quicksort algoritam tada uzima
puna prednost.
To stvara runtime od O (n log n,) n zato moramo učiniti n minus 1.
usporedbe o svakoj generaciji i zapisnik n, jer moramo podijeliti popis
log n puta.
Međutim, u najgorem slučaju, to Algoritam zapravo može biti O (n
kvadrat.) Pretpostavimo da na svakoj generaciji, pivot samo tako dogodi da bude
najmanji ili najveći brojevi sređujemo.
To bi značilo da se razbije popis n puta i odluka n minus 1
usporedbe svaki put.
Dakle, o n kvadrat.
>> Kako možemo unaprijediti način?
Jedan dobar način za poboljšanje metoda je smanjiti vjerojatnost da
runtime je ikada zapravo o n kvadrat.
Zapamtite ovo najgore, najgori scenarij može dogoditi samo kada
stožer izabrao je uvijek najviše ili najniža vrijednost u polju.
Da bi se to je manje vjerojatno da će se dogoditi, možemo pronaći stožer by
Odabirom više elemenata i uzimanje srednju vrijednost.
>> Moje ime je Mark Grozen-Smith, i to je CS50.
>> Radi jednostavnosti, pretpostavimo da su oni stvari su samo cijeli brojevi, ali
Znam da Quicksert -
Quicksert?
Oprostite.
>> Ovdje imamo cijeli brojevi 6, 5, 1, 3, 8, 4, 9.
>> ZVUČNIK 1: Stvarno?
>> ZVUČNIK 2: Nemojte tu stati.
>> ZVUČNIK 1: Stvarno?