MARK GROZEN-SMITH: Sveiki, es esmu Mark Grozen-Smith, un tas ir quicksort. Tāpat kā ievietošanas veida, un burbulis kārtot quicksort ir algoritms šķirošana sarakstu vai masīvs lietas. Vienkāršības labad pieņemsim, ka tie lietas ir tikai veseli skaitļi, bet zina, ka quicksort darbojas vairāk nekā tikai skaitļi. Ātras ir nedaudz sarežģītāka nekā ievietošanas vai burbulis, bet tas ir arī daudz efektīvāku vairumā gadījumu. Pagaidiet otru. Vai viņš tikai saka "visvairāk gadījumos, "ne" viss "? Interesanti, nē. Ne visos gadījumos ir vienādas. Neuztraucieties par šo sīkāk, ja jums neesmu redzējis Big O notācija, tomēr Quicksort ir O (n kvadrātā) algoritms sliktākajā gadījumā, tāpat kā ievietošanas vai burbulis kārtošanas. Tomēr, tā parasti darbojas daudz kā veco analogo m algoritmu. Kāpēc? Mēs saņemam atpakaļ uz šo vēlāk. Bet tagad, pieņemsim tikai mācīties kā quicksort darbi. 

Tātad, pieņemsim iet caur Quicksorting šo masīvs veseli skaitļi no mazākajiem līdz lielākais. Šeit mums ir veseli skaitļi 6, 5, 1, 3, 8, 4, 7, 9 un 2. Pirmkārt, mēs izvēlēties galīgo elementu Tas array - šajā gadījumā divi - un zvanu, ka "griežas". Tālāk, mēs sāk skatīties uz divām lietām - viens, kas ir zemākais rādītājs, ko es ņemšu uzdot kā uzturas uz tiesībām sienas, un, otrkārt, kreisās malas elements, ko es saukšu "pašreizējā elements. "Ko mēs darīsim, ir meklēt visus citus elementus, citus par pagrieziena, un nodot visus elementus mazāks nekā uz šarnīra kreisi no sienas, un visas lielāks nekā šarnīra līdz tiesības uz sienas. Tad, visbeidzot, mēs piliens tapu tiesības uz šo sienu likt to starp visi skaitļi ir mazāki nekā to un visi skaitļi lielāks. 

Tāpēc pieņemsim darīt. Pick up 2, ielieciet pie sienas sākuma, un zvanīt 6 "pašreizējo elements. "Tāpēc mēs vēlamies apskatīt mūsu pašreizējā elements, 6. Un tā kā tas ir lielāks nekā 2, mēs atstāt to tur tiesības uz sienas. Tad mēs pāriet uz apskatīt 5 jo mūsu Pašreizējā elements, un redzēt, ka tas atkal ir lielāks nekā šarnīra, lai mēs atstāt to, ja tas ir no labās sānu sienas. Mums virzīties uz priekšu. Mūsu pašreizējā elements ir tagad 1, un - oh. Šī ir savādāka. Pašreizējais elements tagad ir mazāka nekā šarnīra, tāpēc mēs vēlamies, lai tā pa kreisi sienas. Lai to izdarītu, pieņemsim tikai pārslēgties Pašreizējā elements ar viszemāko indeksu sēž tikai pa labi no sienas. Tagad mēs virzāmies sienas līdz vienam indeksam līdz 1 ir pa kreisi sānu sienas tagad. 

Gaidīt. Es vienkārši sajauca elementus par labajā pusē no sienas, nav I? Neuztraucieties. Tas ir jauki. Vienīgais, kas mums rūp tagad ir tas, ka visi šie elementi tiesības sienas ir lielāks nekā šarnīra. Nav reāla pasūtījums ir pieņemts vēl. 

Tagad atpakaļ uz šķirošanu. Tāpēc mēs turpinām par apskatot pārējais elementiem. Un šajā gadījumā mēs redzam, ka ir nekādi citi elementi ir mazāks nekā eņģēm, tāpēc mēs atstāt tos visus labajā pusē sienas. Visbeidzot, mēs pašreizējā elementa un redzēt, ka tas ir vira. Tagad, tas nozīmē, ka mums ir divas sadaļas masīva, vispirms ir maza uz šarnīra un kreisajā pusē no sienas, bet otrs lielāks nekā šarnīra līdz labajā pusē sienas. Mēs vēlamies, lai šarnīra elements starp divi, un tad mēs zinām, ka griežas ir tās labās galīgais šķiroti vietā. Tāpēc mēs pāriet pirmā elementa labajā pusē sienas ar šarnīra, un mēs zinām, šarnīra ir tā pareizā stāvoklī. 

Tad mēs atkārtojam šo procesu subarrays pa kreisi un pa labi no šarnīra. Tā pēdējā subarray ir tikai viens elements garš, mēs zinām, ka tas jau ir šķiroti, jo, kā jūs varat būt no pasūtīt, ja jūs esat tikai viens elements? Attiecībā uz labo pusi subarray, mēs redzēt, ka šarnīra ir 5, un sienas ir tikai pa kreisi no 6. Un pašreizējais elements arī uzsāk veikt kā 6. Tātad 6 ir lielāks par 5. Mēs atstāt to, ja tas ir no labajā pusē sienas. Tagad pārvietojas uz 3 ir mazāks nekā 5. Tātad, mēs slēdzis ar pirmā elementa tikai tiesības no sienas. Tagad, es pārcēlos sienas augšu vienu. Tagad, pāriet pie 8. 8 ir lielāks par 5, un tāpēc mēs atstāt to. 4 ir mazāka par 5, lai mēs pāriet to. Un vēl. Un vēl. 

Katru reizi, kad mēs atkārtojiet procesu kreisās un labās puses masīva. mēs izvēlēties šarnīra un darīt salīdzinājumus un izveidot vēl vienu līmeni pa kreisi un Tiesības subarrays. Šis rekursīvas zvans turpināsies līdz Mēs beigs, kad mēs esam sadalīt vispārējo masīvs uz tikai subarrays kuru garums ir 1. No turienes, mēs zinām, masīvs ir sakārtots jo katrs elements ir pēc Kādā brīdī, ir eņģēm. Citiem vārdiem, katram elementam, visi skaitļi pa kreisi ir mazāk vērtības un visus numurus tiesības ir lielākas vērtības. 

Šī metode darbojas ļoti labi, ja vērtība izvēlētā asi apmēram vidū diapazons saraksta vērtībām. Tas nozīmētu, ka pēc tam, kad mēs virzāmies elementi apkārt, ir apmēram tik daudz elementi kreisi no šarnīra , kas ir pa labi. Un dalīt-and-iekarot raksturs Tad quicksort algoritms tiek pieņemts pilnībā izmantot. Tas rada izpildlaika O (n log n,) n jo mums ir jādara n mīnus 1 salīdzinājumi par katru paaudzi un žurnālu n jo mums ir sadalīt sarakstu log n reizes. Tomēr, sliktākajā gadījumā, tas algoritms patiesībā var būt O (n kvadrātā.) Pieņemsim, ka katrā paaudzē, griežas tikai tāpēc notiek, mazākā vai lielākā numuri mēs šķirošanu. Tas nozīmētu, sadalot sarakstu n reizes un izgatavošana n mīnus 1 salīdzinājumi katru reizi. Tādējādi, o n brusas. 

Kā mēs varam uzlabot metode? Viens labs veids, kā uzlabot šo metodi, ir samazināt par varbūtību, ka runtime ir kādreiz faktiski o n brusas. Atcerēties šo sliktākais, sliktākajam scenārijam var notikt tikai tad, kad izvēlētā griežas vienmēr augstākais vai zemāko vērtību masīvā. Lai to nodrošinātu, ir mazāk varētu notikt, mēs varam atrast griežas pēc Izvēloties vairākus elementus un ņemot vidējo vērtību. 

Mans vārds ir Marks Grozen-Smith, un tas ir CS50. 

Vienkāršības labad pieņemsim, ka tie lietas ir tikai veseli skaitļi, bet zināt, ka Quicksert - Quicksert? Piedodiet. 

Te mums ir veseli skaitļi 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: Vai tiešām? 

SPEAKER 2: neapstājas tur. 

SPEAKER 1: Vai tiešām?