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