>> MARK GROZEN-Smith: Hi, Ako Mark Grozen-Smith, at ito ay Quicksort.
Tulad lamang ng uri pagpapasok at bubble -uri-uriin, Quicksort ay isang algorithm para sa
sa pag-aayos ng isang listahan o isang hanay ng mga bagay.
Para sa pagiging simple, Ipagpalagay nating hayaan na ang mga bagay lamang integer, ngunit
alam na Quicksort gumagana para sa higit pa sa mga numero.
Quickstart ay isang bit mas komplikado kaysa bubble pagpapasok o, subalit ito ay
magkano din sa mas mahusay na sa karamihan ng mga kaso.
Maghintay ng isang segundo.
Ang ibig sabihin siya lang ang "pinaka- kaso, "hindi" lahat "?
Nang kawili-wili, hindi.
Hindi lahat ng mga kaso ay pareho.
Huwag mag-alala tungkol sa detalye na ito kung ikaw hindi pa nakita malaki pagtatanda Oh, ngunit
Quicksort ay isang O (n nakalapat) algorithm sa pinakamalala, tulad lamang ng
bubble-uri-uriin ang pagpapasok o.
Gayunpaman, ito ay karaniwang gumaganap marami pang iba tulad ng isang lumang analog m algorithm.
Bakit?
Babalikan ka namin sa na mamaya.
Ngunit para sa ngayon, matuto ni lamang ipaalam kung paano gumagana ang Quicksort.
>> Kaya sabihin maglakad sa pamamagitan Quicksorting ito array ng integer mula sa pinakamaliliit
sa pinakamalaking.
Narito mayroon namin ang integer 6, 5, 1, 3, 8, 4, 7, 9, at 2.
Una, pumili namin ang pangwakas na elemento ng ito array - sa kasong ito, dalawang -
at tawagan na ang "pivot." Susunod, namin simulan upang tumingin sa dalawang bagay -
isa, ang pinakamababang index, na kung saan kukunin ko na sumangguni sa bilang naglalagi sa kanan ng
sa pader, at, dalawang, ang pinakakaliwa elemento, na Tatawag ako ng "kasalukuyang
elemento. "Ano kami ay pagpunta sa gawin ay tingnan ang lahat ng iba pang mga elemento, iba pang
kaysa sa mga pivot, at ilagay ang lahat ng mga elemento mas maliit kaysa sa mga pivot sa
iniwan ng mga pader at ang lahat ng mga mas malaki kaysa sa mga pivot sa
kanan ng pader.
Pagkatapos, sa wakas, makikita namin i-drop ang mga pivot karapatan sa na pader upang ilagay ito sa pagitan ng
ang lahat ng mga numero na mas maliit kaysa ito at ang lahat ng mga numero ng mas malaki.
>> Kaya sabihin gawin iyon.
Pumili ng hanggang sa 2, ilagay ang pader sa simula, at tawagan ang 6 na ang "kasalukuyang
elemento. "Kaya gusto namin upang tumingin sa aming kasalukuyang elemento, ang 6.
At dahil ito ay mas malaki kaysa sa 2, mag-iwan namin ito doon sa
kanan ng pader.
Pagkatapos, ilipat namin sa upang tumingin sa ang 5 bilang aming kasalukuyang elemento at makita na ito
ay, muli, mas malaki kaysa sa pivot, kaya kami iwanan ito kung saan ito ay sa kanan
gilid ng pader.
Kami umusad.
Ang aming kasalukuyang mga elemento ay ngayon 1, at - oh.
Ito ay iba ngayon.
Ang kasalukuyang elemento na ngayon na mas maliit sa ang pivot, kaya nais naming ilagay ito
sa kaliwa ng pader.
Upang gawin ito, lumipat na lamang hayaan ang kasalukuyang elemento na may pinakamababang index
pag-upo lamang sa kanan ng pader.
Ngayon, ilipat namin ang mga pader up ng isa index kaya ang 1 ay sa kaliwa
gilid ng pader ngayon.
>> Maghintay.
Lamang halo-halong ko up ang mga elemento sa kanang bahagi ng pader, ginawang hindi ko?
Huwag mag-alala.
Iyon ay pinong.
Ang tanging bagay na mahalaga kami tungkol sa para sa ngayon ay na ang lahat ng mga sangkap na ito sa
kanan ng pader ay mas malaki kaysa sa mga pivot.
Walang aktwal na order pa ipinapalagay.
>> Ngayon, bumalik sa pag-uuri.
Kaya patuloy kami sa pagtingin sa ang natitirang bahagi ng mga elemento.
At sa kasong ito, nakita namin na may mga walang iba pang mga elemento ng mas mababa kaysa sa
ng pivot, kaya mag-iwan namin ang mga ito lahat sa ang kanang bahagi ng pader.
Sa wakas, makakakuha tayo sa kasalukuyang elemento at makita na ito ay ang mga pivot.
Ngayon, na nangangahulugan na mayroon kaming dalawang mga seksyon ng array, ang unang pagkatao
maliit sa pivot at sa kaliwang bahagi ng mga pader, at ang pangalawang pagkatao
mas malaki kaysa sa mga pivot sa kanang bahagi ng pader.
Gusto naming ilagay ang elemento ng mga pivot sa pagitan ng ang dalawang, at pagkatapos ay gagamitin namin alam
na ang mga pivot ay nasa kanan nito huling pinagsunod-sunod lugar.
Kaya lumipat kami sa unang elemento sa kanang bahagi ng pader na may mga pivot,
at alam namin ang mga pivot ng sa sarili karapatan posisyon.
>> Pagkatapos ay ulitin namin ang prosesong ito para sa subarrays sa kaliwa at kanan ng pivot.
Mula noong huling subarray ay isa lamang elemento mahaba, alam namin na mayroon
Uri-uriin dahil kung paano mo maaaring maging out sa umorder kung ikaw ay lamang ng isang elemento?
Para sa kanang bahagi ng subarray, namin makita na ang mga pivot ay 5, at sa pader
ay iniwan lamang ng 6.
At sa kasalukuyang elemento rin nagsisimula out bilang 6.
Kaya 6 ay mas malaki kaysa 5.
Iwanan namin ito kung saan ito ay nasa kanang bahagi ng pader.
Ngayon, gumagalaw sa, 3 ay mas mababa sa 5.
Kaya lumipat kami nito sa unang elemento karapatan lamang ng mga pader.
Ngayon, lumipat ako sa pader up ng isa.
Ngayon, gumagalaw sa sa 8.
8 ay mas malaki kaysa 5, at kaya iwanan namin ito.
Ang 4 Mas mababa sa 5, kaya lumipat namin ito.
At sa.
>> Sa bawat oras na ulitin namin ang proseso sa kaliwa at kanang panig ng array. kami
pumili ng isang pivot at gawin ang mga paghahambing at lumikha ng isa pang antas ng kaliwa at
karapatan subarrays.
Ito recursive tawag ay magpapatuloy hanggang sa maabot namin ang katapusan kapag hindi namin
hinati up ang pangkalahatang array sa lamang subarrays ng haba 1.
Mula doon, alam namin ang array ay pinagsunod-sunod dahil ang bawat elemento ay may, sa
ilang mga punto, naging isang pivot.
Sa ibang salita, para sa bawat elemento, lahat ang mga numero sa bandang kaliwa ay higit na maliit
mga halaga at ang lahat ng mga numero sa karapatang magkaroon ng mas malawak na mga halaga.
>> Pamamaraan na ito ay gumagana nang napakahusay kung ang halaga ng mga pivot pinili ay
humigit-kumulang sa gitna hanay ng mga halaga ng listahan.
Ito ay nangangahulugan na, pagkatapos naming ilipat mga elemento sa paligid, may tungkol sa bilang marami
mga elemento sa kaliwa ng mga pivot bilang mayroong sa kanan.
At ang paghati-hatiin-at-malupig likas na katangian ng Quicksort algorithm ay pagkatapos ay dadalhin
nang husto.
Lumilikha ito ng isang runtime sa mga O (n log n,) ang n dahil mayroon kaming gawin n minus 1
mga paghahambing sa bawat henerasyon at ng log n dahil mayroon kaming upang hatiin ang listahan
mag-log n ulit.
Gayunpaman, sa pinakamasamang sitwasyon, ito algorithm ay maaaring talagang maging O (n
nakalapat.) Ipagpalagay na sa bawat henerasyon, ang pivot kaya lang ang mangyayari sa maging ang
pinakamaliit o ang pinakamalaking ng mga numero na aming pag-uuri.
Ang magiging ibig sabihin nito na pinaghihiwa-hiwalay ang listahan n ang mga oras at paggawa n minus 1
paghahambing bawat solong oras.
Kaya, o ng n nakalapat.
>> Paano namin maaaring mapabuti ang paraan?
Isang mahusay na paraan upang mapabuti ang paraan ay upang i-cut down na sa posibilidad na
ang runtime ay kailanman tunay o ng n nakalapat.
Tandaan ang pinakapangit, pinakamasama sitwasyon kaso Maaari lamang itong mangyari kapag ang
pivot pinili ay palaging ng pinakamataas na o pinakamababang halaga sa array.
Upang matiyak na ito ay hindi malamang na mangyari, maaari naming mahanap ang mga pivot sa pamamagitan ng
pagpili ng maramihang mga elemento at paglalaan ng panggitna halaga.
>> Ang pangalan ko ay Mark Grozen-Smith, at ito ay CS50.
>> Para sa pagiging simple, Ipagpalagay nating hayaan na ang mga bagay lamang integer, ngunit
alam na Quicksert -
Quicksert?
Sorry.
>> Narito mayroon namin ang integer 6, 5, 1, 3, 8, 4, 9.
>> Tagapagsalita 1: Talagang?
>> Tagapagsalita 2: Huwag itigil doon.
>> Tagapagsalita 1: Talagang?