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