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