MARK GROZEN-Smith: Hi, ek is Mark Grozen-Smith, en dit is Quicksort. Net soos inplanting soort en borrel soort, Quicksort is 'n algoritme vir sorteer 'n lys of 'n verskeidenheid van dinge. Vir eenvoud, laat ons veronderstel dat diegene dinge is net heelgetalle, maar weet dat Quicksort werk vir meer as net getalle. Quick is 'n bietjie meer ingewikkeld as inplanting of borrel, maar dit is ook baie meer doeltreffend in die meeste gevalle. Wag 'n sekonde. Het hy net sê "die meeste gevalle ", nie" almal "? Interessant genoeg, no. Nie alle gevalle is dieselfde. Moet nie bekommerd wees oor hierdie detail as jy nie gesien het nie groot O notasie nie, maar Quicksort is 'n O (n kwadraat) algoritme op die ergste, net soos invoeging of borrel soort. Maar dit tipies tree baie meer soos 'n ou analoog m algoritme. Hoekom? Ons sal terug te kry wat later. Maar vir nou, laat ons net leer hoe Quicksort werk. 

So laat loop deur Quicksorting hierdie verskeidenheid van heelgetalle van die kleinste tot die grootste. Hier het ons die heelgetalle 6, 5, 1, 3, 8, 4, 7, 9, en 2. Eerstens, ons kies die finale element van hierdie verskeidenheid - in hierdie geval, twee - en noem dat die "spilpunt." Volgende, ons begin om te kyk na twee dinge - een, die laagste indeks, wat ek sal verwys as bly om die reg van die muur, en twee, die linker element, wat ek sal die "huidige noem element. "Wat gaan ons doen, is om kyk al die ander elemente, ander as die spilpunt, en hy het al die elemente kleiner as die spilpunt van die links van die muur en almal wat groter as die spilpunt van die regs van die muur. Dan, uiteindelik, sal ons die spilpunt daal reg op die muur dit wat tussen al die getalle kleiner as wat dit en al die getalle groter. 

So laat ons dit doen. Haal die 2, sit die muur by die begin, en noem die 6 die "huidige element. "So ons wil om te kyk na ons huidige element, 6. En aangesien dit is groter as die 2, het ons laat dit daar aan die regs van die muur. Dan beweeg ons op om te kyk na die 5 as ons huidige element en sien dat dit is, weer, groter is as die spilpunt, sodat ons laat dit waar dit is op die regte kant van die muur. Ons beweeg op. Ons huidige element is nou 1, en - o. Dit is nou anders. Die huidige element is nou kleiner as die spilpunt, so ons wil om dit te sit aan die linkerkant van die muur. Om dit te doen, laat ons net skakel die huidige element met die laagste indeks sit net aan die regterkant van die muur. Nou, gaan ons die muur een-indeks So het die 1 is op die linker kant van die muur nou. 

Wag nie. Ek het net deurmekaar die elemente op die regterkant van die muur, het ek nie? Moenie bekommerd wees nie. Dit is fyn. Die enigste ding wat ons omgee vir nou is dat al hierdie elemente van die reg van die muur is groter as die spilpunt. Geen werklike einde word aanvaar nie. 

Nou, terug na sorteer. So ons voortgaan op soek na die res van die elemente. En in hierdie geval, sien ons dat daar geen ander elemente minder as die spilpunt, so ons laat hulle almal op die regte kant van die muur. Ten slotte, ons kry om die huidige element en sien dat dit die spilpunt. Nou, dit beteken dat ons twee afdelings van die skikking, die eerste wese klein op die spilpunt en aan die linkerkant van die muur en die tweede wese groter as die spilpunt van die regterkant van die muur. Ons wil die spilpunt element wat tussen Die twee, en dan sal ons weet dat die spilpunt is in sy reg finale gesorteer plek. So skakel ons die eerste element op die regterkant van die muur met die spilpunt, en ons weet die spilpunt se in sy regte posisie. 

Ons herhaal hierdie proses vir die subarrays links en regs van die spilpunt. Sedert die laaste subarray is net een element lang, weet ons wat reeds gesorteer, want hoe kan jy uit bestel as jy net een element? Vir die regterkant van die subarray ons sien dat die spilpunt is 5, en die muur is net links van die 6. En die huidige element ook begin as die 6. 6 is dus meer as 5. Ons laat dit waar dit op die regterkant van die muur. Nou, skuif oor, 3 is minder as 5. So het ons skakel dit met die eerste element net regs van die muur. Nou, ek het die muur tot een. Nou, skuif oor na die 8. 8 is groter as 5, en so het ons los dit. Die 4 is minder as 5, dus skakel dit. En op. En op. 

Elke keer wanneer ons herhaal die proses op die links en regs van die skikking. ons kies 'n spilpunt en doen die vergelykings en die skep van 'n ander vlak van links en reg subarrays. Dit rekursiewe oproep sal voortgaan totdat bereik ons ​​die einde wanneer ons verdeel die algehele skikking in net subarrays van lengte 1. Van daar is, weet ons die skikking gesorteer want elke element het, op 'n sekere punt, is 'n spilpunt. Met ander woorde, vir elke element, al die syfers aan die linkerkant is mindere waardes en al die getalle tot die reg hê om 'n groter waardes. 

Hierdie metode werk baie goed as die waarde van die spilpunt gekies is ongeveer in die middel omvang van die lys waardes. Dit sou beteken dat, nadat ons beweeg elemente rond, is daar omtrent net soveel elemente aan die linkerkant van die spilpunt as daar aan die regterkant. En die verdeel-en-heers aard van die Quicksort algoritme word dan geneem volle voordeel van. Dit skep 'n looptyd van O (n teken n,) die n, want ons het om te doen n minus 1 vergelykings op elke generasie en log n, want ons het die lys te verdeel log n keer. Maar, in die ergste gevalle, is hierdie algoritme kan eintlik O (n kwadraat.) Veronderstel op elke generasie, die spilpunt net so gebeur te wees om die kleinste of die grootste van die getalle ons sorteer. Dit sou beteken dat die lys af te breek n keer en maak n minus 1 vergelykings elke keer. So, o N vierkantig. 

Hoe kan ons die metode verbeter? Een goeie manier om die metode te verbeter, is af te sny op die waarskynlikheid dat die runtime is ooit werklik o van n kwadraat. Onthou dit ergste, ergste geval scenario kan net gebeur wanneer die spilpunt gekies is altyd die hoogste of laagste waarde in die skikking. Om te verseker dat dit is minder geneig om te laat gebeur, ons kan die spilpunt vind deur die keuse van verskeie elemente en die neem van die gemiddelde waarde. 

My naam is Mark Grozen-Smith, en dit is CS50. 

Vir eenvoud, laat ons veronderstel dat diegene dinge is net heelgetalle, maar weet dat Quicksert - Quicksert? Jammer. 

Hier het ons die heelgetalle 6, 5, 1, 3, 8, 4, 9. 

Spreker 1: Regtig? 

Spreker 2: stop nie daar nie. 

Spreker 1: Regtig?