>> MARK GROZEN-Smith: Živjo, jaz sem Mark Grozen-Smith, in to je hitro urejanje.
Tako kot vstavljanja vrste in mehurček sort, hitro urejanje, je algoritem za
sortiranje seznam ali paleto stvari.
Zaradi enostavnosti predpostavimo, da tisti, stvari so le cela števila, vendar
vedo, da hitro urejanje dela za več kot le številke.
Začeti je malce bolj zapleteno od vstavitve ali mehurček, vendar je
tudi veliko bolj učinkovit V večini primerov.
Počakaj malo.
Ali je pravkar rekel "najbolj primerov, "ne" vse "?
Zanimivo je, št.
Ne v vseh primerih enaka.
Ne skrbite za to podrobnost, če ti niso videli velik O zapis še ni, vendar
Hitro urejanje je O (n kvadrat) algoritem v najslabšem primeru, tako kot
vstavljanje ali bubble sort.
Vendar pa običajno deluje bolj kot stari analogni m algoritem.
Zakaj?
Bomo dobili nazaj kasneje.
Ampak za zdaj, kaj je pravkar izvedeli, kako hitro urejanje deluje.
>> Torej, kaj je sprehod skozi Quicksorting to matrika celih števil od najmanjše
do največjega.
Tukaj imamo cela števila 6, 5, 1, 3, 8, 4, 7, 9, in 2.
Najprej smo izbrali končni element To polje - v tem primeru dve -
in pozivajo, da "pivot". Nato smo začnete iskati na dveh stvareh -
ena, najmanjši indeks, ki bom se nanašajo kot bivanje na desni strani
steno, in dva, levega element, ki sem ga pokličem "tok
element. "Kaj bomo storili, je poglej vse druge elemente, druge
kot pivot, in dal vse elemente manjši od vrtišča do
levo steno in vse tiste, večji od vrtišča do
desni strani stene.
Potem, na koncu, bomo padec pivot prav na tej steni, da ga med
vse številke manjši, kot je in vse številke večje.
>> Torej, kaj je to.
Pick up 2, dal na steno se začne, in pokličite 6 "tekoče
element. "Zato smo želeli videti na Naš trenutni element, 6.
In ker je večji od 2, smo ga pusti tam
desni strani stene.
Potem pa gremo naprej gledati na 5 kot naš Sedanji element in videli, da je to
je spet večji od vrtišča, tako da pustite, kjer je na desni strani
strani stene.
Gremo naprej.
Naš trenutni element Zdaj 1, in - oh.
To je zdaj drugačna.
Sedanji element je sedaj manjša od pivot, zato smo želeli, da bi ga
na levi strani stene.
Če želite to narediti, kaj je samo stikalo Trenutna element z najmanjšim indeksom
sedi samo na desni steni.
Zdaj pa gremo v steno do enega indeksa do 1 je na levi
strani zidu sedaj.
>> Čakati.
Pravkar sem pomešal elemente na desna stran od stene, kajne?
Ne skrbite.
To je v redu.
Edina stvar, ki nam je mar za zdaj je, da so vsi ti elementi na
Pravica do stene, večji od vrtišča.
Ne Dejanski vrstni red je še domneva.
>> Zdaj pa nazaj k sortiranju.
Tako da bomo še naprej gledaš ostali elementi.
In v tem primeru vidimo, da obstajajo drugih elementov najmanj
pivot, tako da smo jih vsi na dopustu desna stran od stene.
Končno smo prišli do trenutnega elementa in vidimo, da je nihalna.
No, to pomeni, da imamo dva oddelki niz, prvega počutje
majhna na čepom in na levi strani stene, drugi pa
večji od vrtišča do desna stran od stene.
Želimo postaviti pivot element med dva, in potem bomo vedeli,
da je nihalna v desnem Končni razvrščeni mesto.
Tako smo preklopite na prvi element na desna stran stene s čepom,
in vemo pivot je v pravem položaju.
>> Mi ponovite ta postopek za subarrays levo in desno od pivot.
Ker zadnja subarray je le ena element dolgo vemo, da je že
sortirani, ker kako si lahko iz odredi, če si samo en element?
Za desni strani subarray smo vidimo, da je nihalna 5, in steno
je pravkar zapustil v 6.
In trenutni element tudi Začne se kot 6.
Torej 6 večji od 5.
Mi pustimo, kjer je na desna stran od stene.
Zdaj pa se gibljejo na, 3 manj kot 5.
Zato smo ga vključite s prvim elementom ravno prav stene.
Zdaj pa sem se preselil v steno navzgor za eno mesto.
Zdaj pa se gibljejo na 8..
8 je večja od 5, in zato smo ga zapustiti.
4 je manj kot 5, tako da smo jo vključite.
In naprej.
>> Vsakič, ko postopek ponovite na levi in ​​desni strani matrike. smo
Izberite pivot in narediti primerjave in ustvariti novo raven levo in
desna subarrays.
Ta rekurzivni klic, se bo nadaljevalo, dokler pridemo do konca, ko smo se
razdeli celotno paleto v le subarrays dolžine 1.
Od tam pa vemo, matrika je razvrščen saj ima vsak element, na
nekatere točke, je pivot.
Z drugimi besedami, za vsak element, vsi številke na levi so manj
vrednote in vse številke na pravico imajo večje vrednosti.
>> Ta metoda deluje zelo dobro, če vrednost izbranega vrtilnega
približno na sredini razpon vrednot seznama.
To bi pomenilo, da je, potem ko se gibljemo elementi okrog, obstaja približno toliko
elementi na levi strani vrtišča kot so na desno.
In razkorak-in-vladaj narava Hitro urejanje algoritem se nato upošteva
celoti izkoristijo.
To ustvarja runtime od O (n log n) n, ker moramo narediti n minus 1
primerjave za vsako generacijo in se prijavite n ker moramo razdeliti seznam
log n-krat.
Vendar pa v najslabšem primeru, to Algoritem lahko dejansko O (n
kvadrat.) Recimo, da na vsaki generaciji, pivot prav tako se zgodi, da bo
najmanjši ali največji številke smo sortiranje.
To bi pomenilo zrušijo seznam n-krat in izdelava n minus 1
primerjave vsak čas.
Tako O N kvadrat.
>> Kako lahko izboljšamo način?
En dober način, da bi izboljšali način je naj bi zmanjšali verjetnost, da
teka je doslej dejansko o n kvadrat.
Zapomni si to najslabši v najslabšem primeru se lahko zgodi le, če
Izbrani pivot je vedno najvišja ali najnižja vrednost v matriki.
Da bi zagotovili, da je to manj verjetno, da se zgodi, najdemo pivot, ki jih
izbiro več elementov in ob srednjo vrednost.
>> Moje ime je Mark Grozen-Smith, in to je CS50.
>> Zaradi enostavnosti predpostavimo, da tisti, stvari so le cela števila, vendar
vedeti, da Quicksert -
Quicksert?
Žal mi je.
>> Tukaj imamo cela 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Res?
>> SPEAKER 2: Ne ustavi tam.
>> SPEAKER 1: Res?