MARK GROZEN-SMITH: Hæ, ég er Mark Grozen-Smith, og þetta er Quicksort. Rétt eins og Innsetningarröðun og kúla raða, Quicksort er reiknirit fyrir flokkun lista eða fylki af hlutum. Fyrir einfaldleiki, við skulum gera ráð fyrir að þeir hlutirnir eru bara heiltölur, en vita að Quicksort virkar fyrir meira en bara tölur. QuickStart er dálítið flóknara en innsetning eða kúla, en það er Einnig mun skilvirkari í flestum tilfellum. Bíddu við. Gerði hann að segja bara "mest tilvikum, "ekki" allt "? Athyglisvert, nr. Ekki öll tilfelli eru þau sömu. Ekki hafa áhyggjur af þessu smáatriðum ef þú hef ekki séð Big O tákn enn, en Quicksort er O (n í öðru veldi) reiknirit í versta falli, rétt eins og innsetning eða kúla tegund. Hins vegar virkar það yfirleitt mikið meira eins og gamlan flaumi m reiknirit. Hvers vegna? Við munum fá til baka til það síðar. En nú, við skulum bara læra hvernig Quicksort virkar. 

Svo skulum ganga í gegnum Quicksorting þetta array heiltalna frá minnstu til stærsta. Hér höfum við heiltölur 6, 5, 1, 3, 8, 4, 7, 9, og 2. First, velja okkur Lokaþáttur þetta array - í þessu tilfelli, tveir - og kalla að "pivot." Næst, við byrja að líta á tvo hluti - einn, lægsta vísitölu, sem ég mun vísa til sem dvelja til hægri vegg, og, tveir, að leftmost þáttur, sem ég mun kalla "núverandi þáttur. "Það sem við erum að fara að gera er að líta alla aðra þætti, önnur en völtur, og setja alla þætti minni en snúist í til vinstri á veggnum og allir þeir stærri en snúist í hægri á vegg. Þá loks munum við falla pivot rétt á þessi veggur til að setja það á milli allar tölur minni en það og allar tölur stærri. 

Svo skulum gera það. Taka upp 2, setti vegg á farin og hringdu í 6 "núverandi þáttur. "Þannig að við viljum líta á Núverandi þáttur okkar, 6. Og þar sem það er stærri en 2, láta við það þar til hægri á vegg. Þá færa okkur á að líta á 5 eins og okkar Núverandi þáttur og sjá að þetta er, aftur, stærri en snúningspinnann, þannig að við leyfi það þar sem það er á hægri megin við vegginn. Við fara. Núverandi þáttur okkar er nú 1 og - ó. Þetta er nú öðruvísi. Núverandi þátturinn er nú minni en völtur, þannig að við viljum setja það vinstra megin við vegginn. Til að gera þetta, við skulum skipta bara Núverandi þáttur með lægsta vísitölu situr bara til hægri vegg. Nú, færa okkur vegginn upp einni vísitölu svo er 1 til vinstri megin við vegginn núna. 

Bíddu. Ég blanda bara upp hluti á hægri hlið vegg, gerði ég ekki? Ekki hafa áhyggjur. Það er allt í lagi. Það eina sem okkur er annt um að nú er að öll þessi atriði til að til hægri á vegg eru stærri en völtur. Enginn raunverulegur röð er enn gert ráð fyrir. 

Nú, aftur að flokka. Svo við höldum áfram á að horfa á restin af þeim þáttum. Og í þessu tilfelli, má sjá að það eru Engar aðrir þættir minna en völtur, svo við leggjum þau öll á hægra megin á veggnum. Loks fáum við að núverandi frumefni og sjá að það er völtur. Nú, það þýðir að við höfum tvo kafla í fylkinu, Fyrsta vera lítið á völtur og á vinstri hlið á veggnum, og annað sem stærri en snúist í hægri megin við vegginn. Við viljum setja völtur þáttur milli tveir, og þá munum við vita skagar er í rétti sínum Endanleg raðað staður. Þannig að við skipta fyrsta atriði á hægra megin á vegg með Pivot, og við vitum völtur er í rétta stöðu. 

Við endurtaka þá er þetta ferli til að vinna subarrays vinstri og hægri á völtur. Frá því að síðasta subarray er aðeins eitt þáttur lengi, við vitum að er nú þegar Raðað því hvernig er hægt að vera út af panta ef þú ert aðeins einn þáttur? Fyrir hægri hlið subarray, við sjá skagar er 5, og vegg er bara eftir af 6. Og núverandi þáttur líka byrjar út eins og 6. Svo er 6 meiri en 5. Við leggjum það þar sem það er á hægri megin við vegginn. Nú, að færa á, 3 er minna en 5. Þannig að við að skipta um það með fyrsta frumefni bara rétt á veggnum. Nú flutti ég vegginn upp einn. Nú, flutti í 8. 8 er meiri en 5, og svo við leggjum það. The 4 er minna en 5, þannig að við að skipta á það. Og á. Og á. 

Hvert skipti sem við endurtökum ferlið á vinstri og hægri hliðar í fylkinu. við velja pivot og gera samanburð og búa til annan stigi til vinstri og rétt subarrays. Þetta endurkvæma hringja mun halda áfram þar til við náum að enda þegar við höfum skipt upp í heild array inn bara subarrays af lengd 1. Þaðan vitum við array er raðað því hver þáttur hefur á einhverjum tímapunkti, verið völtur. Með öðrum orðum, fyrir sérhver þáttur, allir Tölurnar til vinstri eru minni gildi og allar tölur til að rétt hafa meiri gildum. 

Þessi aðferð virkar mjög vel ef gildi snúningspinnann valið er um það bil í miðjunni svið af listanum gildum. Þetta myndi þýða að eftir að við færa þættir í kring, þar um eins og margir þættir til vinstri á völtur eins og það eru til hægri. Og skipta-og-sigra eðli af Quicksort algrím er síðan leyst fullur kostur af. Þetta skapar Runtime af O (n log n,) n vegna þess að við verðum að gera n mínus 1 samanburð á hverri kynslóð og tengja n vegna þess að við verðum að skipta lista log n sinnum. Hins vegar, í versta tilfelli, þetta Reiknirit geta raunverulega vera O (n ferningur.) Segjum á hverri kynslóð, völtur gerist bara svo að vera minnstu eða stærsta af tölur sem við erum að flokka. Þetta myndi þýða að brjóta niður listann N sinnum og gerð n mínus 1 samanburður hvert eitt sinn. Þannig, o af n í öðru veldi. 

Hvernig getum við bætt aðferð? Ein leið til að bæta aðferð er að skera niður á líkum á að The Runtime er alltaf í raun o af n í öðru veldi. Muna þetta versta versta falli getur aðeins gerst þegar völtur valið er alltaf hæsta eða lægsta gildi í array. Til að tryggja þetta er minna líklegur til að gerast, við getum fundið ás með velja marga þætti og taka miðgildi. 

Mitt nafn er Mark Grozen-Smith, og þetta er CS50. 

Fyrir einfaldleiki, við skulum gera ráð fyrir að þeir hlutirnir eru bara heiltölur, en vita að Quicksert - Quicksert? Sorry. 

Hér höfum við heiltölur 6, 5, 1, 3, 8, 4, 9. 

Ræðumaður 1: Really? 

Ræðumaður 2: Ekki hætta þar. 

Ræðumaður 1: Really?