>> MARK GROZEN-SMITH: Hi, Im 'Mark Grozen-Smith, ac mae hyn yn Quicksort.
Yn union fel math mewnosod a swigod didoli, Quicksort yn algorithm ar gyfer
didoli restr neu amrywiaeth o bethau.
Er hwylustod, gadewch i ni dybio bod y rhai pethau yn unig gyfanrifau, ond
gwybod bod Quicksort yn gweithio i mwy na dim ond rhifau.
CychwynChwim yn ychydig yn fwy cymhleth na gosod neu swigod, ond mae'n
hefyd yn llawer mwy effeithlon yn y rhan fwyaf o achosion.
Aros Eiliad.
A oedd yn dim ond dweud "y rhan fwyaf achosion, "nid" bawb "?
Yn ddiddorol, dim.
Nid yw pob achos yr un fath.
Peidiwch â phoeni am y manylion hyn os ydych yn Nid yw wedi gweld O nodiant mawr eto, ond
Quicksort yn O (n sgwâr) algorithm ar y gwaethaf, yn union fel
gosod neu fath swigen.
Fodd bynnag, mae'n fel arfer yn gweithredu llawer mwy fel analog hen m algorithm.
Pam?
Byddwn yn mynd yn ôl at hynny'n ddiweddarach.
Ond am y tro, gadewch i ni dim ond yn dysgu sut Quicksort gweithio.
>> Felly, gadewch i ni gerdded drwy'r Quicksorting hwn amrywiaeth o gyfanrifau o'r lleiaf
i'r mwyaf.
Yma, mae gennym y cyfanrifau 6, 5, 1, 3, 8, 4, 7, 9, a 2.
Yn gyntaf, rydym yn dewis elfen olaf amrywiaeth hon - yn yr achos hwn, dwy -
ac yn galw bod y "colyn." Nesaf, mae dechrau edrych ar ddau beth -
un, y mynegai isaf, a byddaf yn cyfeirio fel aros i'r dde o'r
y wal, ac, dau, y leftmost elfen, y byddaf yn galw y "presennol
elfen. "Yr hyn yr ydym yn mynd i wneud yw edrych yr holl elfennau eraill, ac
na'r colyn, ac yn rhoi holl elfennau llai na'r colyn i'r
i'r chwith y wal a phawb fwy na'r colyn i'r
hawl y wal.
Yna, yn olaf, byddwn yn gollwng y colyn dde ar y wal i roi rhwng
holl rifau llai nag y a'r holl rhifau mwy.
>> Felly, gadewch i ni wneud hynny.
Codwch y 2, rhowch y wal yn y dechrau, a ffoniwch y 6 "presennol
elfen. "Felly rydym am edrych ar ein bodd yn bresennol, y 6.
Ac ers ei fod yn fwy na'r 2, rydym yn ei adael yno i'r
hawl y wal.
Yna, rydym yn symud ymlaen i edrych ar y 5 fel ein elfen gyfredol ac yn gweld bod hyn yn
yw, unwaith eto, yn fwy na'r colyn, felly rydym adael lle mae'n ar y dde
ochr y wal.
Rydym yn symud ymlaen.
Ein elfen presennol yn nawr 1, ac - oh.
Mae hyn yn wahanol yn awr.
Yr elfen presennol yn awr yn llai na y colyn, felly rydym yn awyddus i roi
i'r chwith y wal.
I wneud hyn, gadewch i ni dim ond newid y elfen bresennol gyda'r mynegai isaf
eistedd ychydig i'r dde o'r wal.
Nawr, rydym yn symud y wal i fyny un mynegai felly mae'r 1 ar y chwith
ochr y wal yn awr.
>> Aros.
Fi jyst cymysgu elfennau ar y ochr dde y wal, nid oedd i?
Peidiwch â phoeni.
Mae hynny'n iawn.
Yr unig beth yr ydym yn gofalu am ar hyn o bryd yw bod yr holl elfennau hyn at y
hawl y wal yn fwy o faint na'r colyn.
Unrhyw drefn gwirioneddol tybir eto.
>> Yn awr, yn ôl i didoli.
Felly, rydym yn parhau i edrych ar gweddill yr elfennau.
Ac yn yr achos hwn, rydym yn gweld bod unrhyw elfennau eraill llai na'r
colyn, felly rydym yn gadael nhw i gyd ar yr ochr dde y wal.
Yn olaf, rydym yn cael yr elfen presennol a gweld ei fod yn y colyn.
Yn awr, mae hynny'n golygu bod gennym ddau adrannau y rhesi, sef y cyntaf
bychan ar y colyn ac ar yr ochr chwith y wal, a'r ail lles
fwy na'r colyn i'r ochr dde y wal.
Rydym eisiau rhoi'r elfen colyn rhwng y ddau, ac yna byddwn yn gwybod
bod y colyn yn ei rinwedd ei lle ddidoli terfynol.
Felly, rydym yn newid yr elfen cyntaf ar y ochr dde y wal gyda'r colyn,
ac rydym yn gwybod y colyn yn yn ei safle cywir.
>> Yna, rydym yn ailadrodd y broses hon ar gyfer y subarrays chwith a dde o'r colyn.
Ers y subarray olaf ond un elfen hir, rydym yn gwybod bod eisoes
ddidoli oherwydd sut y gallwch fod allan o archebu os ydych dim ond un elfen?
Ar gyfer yr ochr dde y subarray, rydym yn gweld bod y colyn yw 5, ac mae'r wal
yn cael ei adael un o'r 6.
A'r elfen presennol hefyd yn yn dechrau allan fel yr 6.
Felly, 6 yn fwy na 5.
Rydym yn ei adael lle y mae ar y ochr dde y wal.
Yn awr, gan symud ymlaen, 3 yn llai na 5.
Felly, rydym yn newid gyda'r elfen gyntaf jyst dde y wal.
Yn awr, yr wyf yn symud y wal i fyny un.
Yn awr, gan symud ymlaen i'r 8.
8 yn fwy na 5, ac felly rydym yn ei adael.
Mae'r 4 yn llai na 5, felly rydym yn newid hynny.
Ac ymlaen.
>> Bob tro y byddwn yn ailadrodd y broses ar y ochr chwith a dde y rhesi. rydym
dewis golyn a gwneud y cymariaethau ac yn creu lefel arall o chwith a
subarrays cywir.
Bydd hyn yn galw ailadroddus yn parhau hyd nes rydym yn cyrraedd y diwedd pan rydym wedi
rhannu yr amrywiaeth gyffredinol i dim ond subarrays o hyd 1.
Oddi yno, rydym yn gwybod y casgliad yn cael ei datrys oherwydd y mae pob elfen sydd, ar
ryw adeg, wedi bod yn colyn.
Mewn geiriau eraill, ar gyfer pob elfen, pob y rhifau i'r chwith yn llai
gwerthoedd a'r holl rhifau i'r dde yn cael mwy o werthoedd.
>> Mae'r dull hwn yn gweithio'n dda iawn os bydd y gwerth y colyn a ddewiswyd yn
tua yn y canol amrediad y gwerthoedd rhestr.
Byddai hyn yn golygu, ar ôl i ni symud elfennau o gwmpas, yno am gymaint o
elfen i'r chwith y colyn gan fod i'r dde.
A natur rhannu-a-goncro y Yna algorithm Quicksort yn cael ei gymryd
manteisio'n llawn ar.
Mae hyn yn creu Rhedeg o O (n log n,) y n oherwydd rhaid inni wneud n minws 1
cymariaethau ar bob cenhedlaeth a log n oherwydd rhaid inni rannu'r rhestr
log amseroedd n.
Fodd bynnag, yn yr achosion gwaethaf, mae hyn yn Gall algorithm mewn gwirionedd fod yn O (n
sgwâr.) Tybiwch ar bob cenhedlaeth, y colyn ond fel y digwydd i fod yn
lleiaf neu y mwyaf o niferoedd rydym yn didoli.
Byddai hyn yn golygu torri i lawr y rhestr n amseroedd a gwneud n minws 1
cymariaethau bob tro.
Felly, o n sgwâr.
>> Sut allwn ni wella dull?
Un ffordd da i wella dull yn i dorri i lawr ar y tebygolrwydd y
y runtime byth mewn gwirionedd o n sgwâr.
Cofiwch hyn, y senario achos gwaethaf gwaethaf dim ond yn digwydd pan fydd y
colyn a ddewiswyd bob amser yn uchaf neu werth isaf yn y rhesi.
Er mwyn sicrhau bod hyn yn llai tebygol o ddigwydd, gallwn ddod o hyd y colyn gan
dewis elfennau lluosog a cymryd y gwerth canolrif.
>> Fy enw i yw Mark Grozen-Smith, ac mae hyn yn CS50.
>> Er hwylustod, gadewch i ni dybio bod y rhai pethau yn unig gyfanrifau, ond
gwybod bod Quicksert -
Quicksert?
Mae'n ddrwg gennym.
>> Yma, mae gennym y cyfanrifau 6, 5, 1, 3, 8, 4, 9.
>> SIARADWR 1: Really?
>> SIARADWR 2: Peidiwch â rhoi'r gorau i yno.
>> SIARADWR 1: Really?